Языки и трансляции. Мартыненко Б.К. - 4 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

3
ОГЛАВЛЕНИЕ
Предисловие к первому изданию...........................................................................................5
Предисловие ко второму изданию .........................................................................................7
Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ ...................................................... 8
Глава 1. Языки и их представление.................................................................................—
§ 1.1. Алфавиты и языки .......................................................................................................—
§ 1.2. Представление языков...................................................................................................9
Упражнения............................................................................................................................12
Глава 2. Грамматики ..........................................................................................................13
§ 2.1. Мотивировка ................................................................................................................—
§ 2.2. Формальное определение грамматики ......................................................................14
§ 2.3. Типы грамматик...........................................................................................................17
§ 2.4. Пустое предложение....................................................................................................20
§ 2.5. Рекурсивность контекстно-зависимых грамматик ...................................................22
§ 2.6. Деревья вывода в контекстно-свободных грамматиках ..........................................23
Упражнения............................................................................................................................26
Глава 3. Конечные автоматы и регулярные грамматики...........................................28
§ 3.1. Конечный автомат .......................................................................................................—
§ 3.2. Отношения эквивалентности и конечные автоматы ................................................30
§ 3.3. Недетерминированные конечные автоматы .............................................................33
§ 3.4. Конечные автоматы и языки типа 3...........................................................................36
§ 3.5. Свойства языков типа 3...............................................................................................38
§ 3.6. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов .....43
Упражнения............................................................................................................................45
Глава 4. Контекстно-свободные грамматики
...........................................................46
§ 4.1. Упрощение контекстно-свободных грамматик ........................................................—
§ 4.2. Нормальная форма Хомского.....................................................................................50
§ 4.3. Нормальная форма Грейбах........................................................................................53
§ 4.4. Разрешимость конечности контекстно-свободных языков .....................................57
§ 4.5. Свойство самовставленности .....................................................................................61
§ 4.6. ε-Правила в контекстно-свободных грамматиках ....................................................63
§ 4.7. Специальные типы контекстно-свободных языков и грамматик ...........................65
Упражнения............................................................................................................................66
Глава 5. Магазинные автоматы .......................................................................................69
§ 5.1. Неформальное описание .............................................................................................—
§ 5.2. Формальное определение............................................................................................70
§ 5.3. Недетерминированные магазинные автоматы и контекстно-свободные языки....73
Упражнения............................................................................................................................80
Глава 6. Машины Тьюринга.............................................................................................82
§ 6.1. Неформальное и формальное описания ....................................................................—
§ 6.2. Методы построения машин Тьюринга ......................................................................85
§ 6.3. Машина Тьюринга как процедура .............................................................................92
§ 6.4. Модификации машин Тьюринга ...............................................................................93
§ 6.5. Ограниченные машины Тьюринга, эквивалентные основной модели ..................99
Упражнения..........................................................................................................................102
Глава 7. Машины Тьюринга: проблема остановки, языки типа 0 ........................104
§ 7.1. Универсальная машина Тьюринга .............................................................................—
§ 7.2. Неразрешимость проблемы остановки....................................................................110
§ 7.3. Класс рекурсивных множеств ..................................................................................112
§ 7.4. Машины Тьюринга и грамматики типа 0................................................................113
Упражнения..........................................................................................................................117

Страницы