ВУЗ:
Составители:
ОГЛАВЛЕНИЕ:
Введение
0.1 Объекты изучения и задачи курса……………………………………………………….4
0.2 Понятие формальной системы……………………………………………………………5
0.3 Интуитивное понятие алгоритма………………………………………………………...6
0.4 Понятие языка………………………………………………………………………………8
0.5 Понятие программы………………………………………………………………………10
0.6 Понятие транслятора……………………………………………………………………..11
1.Алгоритмические системы
1.1 Основные понятия и определения……………………………………………………...12
1.2 Комбинаторные системы………………………………………………………………...15
1.3 Соответствие между полутуэвской и нормальной системами………………………17
1.4 Нормальные алгоритмы Маркова……………………………………………………...20
2. машина Тьюринга
2.1 Состав и работа машины Тьюринга……………………………………………………23
2.2 Анализ и синтез машин Тьюринга……………………………………………………..25
2.3 Диаграммы Тьюринга……………………………………………………………………27
2.4 Машины Тьюринга и вычислимые функции…………………………………………30
2.5 Геделевский номер Машины Тьюринга……………………………………………….32
2.6 Рекурсивные и рекурсивно перечислимые множества………………………………34
2.7 Неразрешимость проблемы остановки для произвольных машин Тьюринга…...36
2.8 Комбинаторные системы и машины Тьюринга………………………………………38
3. Формальные грамматики и языки
3.1 Порождающие грамматики……………………………………………………………...40
3.2 Контекстно свободные грамматики…………………………………………………….43
3.3 Автоматы с магазинной памятью………………………………………………………48
3.4 Автоматные грамматики и языки……………………………………………………...52
3.5 Конечные автоматы и способы их задания……………………………………………53
3.6 Алгебры событий. Представление событий в автоматах……………………………59
3.7 Взаимосвязь автоматов и языков……………………………………………………….63
ЗАКЛЮЧЕНИЕ………………………………………………………………………………..65
ЛИТЕРАТУРА……...………………………………………………………………………….68
