Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
291
[1963b] On context-free languages and push-down automata, Information and control, 6, № 3, 246—264
Определение автомата с магазинной памятью, языки Дика Янгер (YoungerD Н)
*[1967] Recognition and parsing of context-tree languages in time n3, Information and control, 10, № 2, 189—209. (Перевод: в сб. «Проблемы математической логики», M., 1970, 344—362.) оглавление
Предисловие редактора перевода ................5
От авторов.........................7
Предисловие .......................9
ЧАСТЬ Г предварительные сведения из логики и алгебры
Глава I. Слова (цепочки). Полугруппы. Языки...........13
§ 1.1. Свободная полугруппа................13
§ 1.2. Операции над словами................18
§ 1.3. Языки ......................23
§ 1.4. Упражнения....................26
Глава II. Общие сведения о формальных системах..........80
§ 2.1. Описание исчисления высказываний на интуитивном уровне . . 30
§ 2.2. Понятие формальной системы.............37
§ 2.3. Формализованный вариант исчисления высказываний .... 42
§ 2.4. Определение формальной системы...........46
Глава III. Комбинаторные системы................49
§ 3.1. Определение комбинаторных систем...........49
§ 3.2. Нормальные системы ................57
§ 33 Упражнения ...................61
§ 3.4. Независимость от алфавита..............61
Глава IV. Алгоритмы. Машины Тьюринга.............64
§ 4.1. Алгоритмы ....................64
§ 4.2. Машины Тьюринга . . . ,.............68
§ 4.3. «Численные» машины Тьюринга............76
§ 4.4. Упражнения ..........................79
Глава V Вычислимость и разрешимость..............81
§ 51 Исчисление функций.................81
§ 5.2 Операции над функциями............................83
§ 5.3. Метод Гёделя...................86
§ 5.4. Рекурсивные и рекурсивно перечислимые множества . . , . 89
§ 5.5 Замечания и дополнения...............93
Глава VI. Комбинаторные системы и машины Тьюринга: неразрешимые проблемы ......................69
§ 6.1. Комбинаторные системы и машины Тьюринга.......99
$ 6.2. Неразрешимые проблемы ................1Q5 Оглавление
293
часть ii. некоторые замечательные классы языков Глава VII. Контекстно-свободные языки (языки Хомского). общая характе-
ристика и основные свойства..............112
§ 7.1. Грамматика и описание синтаксических структур .....112
§ 7.2. Определения. Распознаваемые свойства.........116
§ 7 3. Свойства замкнутости ... ............123
§ 7.4. Специальные классы КС-языков............126
§ 7.6. Упражнения ...................129
Глава VIII. Нераспознаваемые свойства КС-грамматик........130
§ 8 1. Проблемы, связанные с пересечением..........130
§ 8 2. Проблемы, связанные с неоднозначностью........133
§ 8 3. Существенная неоднозначность минимальных линейных языков 139
Глава IX. Автоматы с магазинной памятью.............143
§ 9.1. Автоматы, допускающие языки.............143
§ 9.2. Автоматы, порождающие языки...........149
§ 9.3. Класс языков, допускаемых (порождаемых) МП-автоматами . 161 §9 4. Приложения КС-языков ...............155
Глава X Автоматные языки и конечные автоматы..........169
§ 10 1. А-грамматики ...................159
§ 10.2. Конечные автоматы ................162
§ 10.3. Некоторые обобщения и видоизменения конечных автоматов . 166
§ 10 4. Свойства замкнутости Представление А-языков по Клини . . 168
§ 10 5. А-языки и КС-языки................171
§ 10 6. Односторонние конечные преобразователи........172
Глава XI. Задание языков с помощью систем уравнений........176
§ 11.1. Функции, аргументами и значениями которых являются языки 175 § 112. Языки и формальные степенные ряды.........189
Глава XII. Грамматики непосредственно составляющих Автоматы с линейно
ограниченной памятью ................ 194
§ 12.1. Грамматики непосредственно составляющих (НС-грамматики) 194
§ 12.2. Линейно ограниченные автоматы...........196
§ 12.3 Классификация автоматов..............199
§ 12.4 Упражнения ...................201
часть iii. алгебраический подход
Глава XIII. Гомоморфизмы полугрупп ..............202
§ 13.1. Произвольные полугруппы..............202
§ 13 2. Конгруэнция и эквивалентности, сопоставляемые языку . . . 207 § 13.3. Понятия, связанные с кодами.............212
Глава XIV. Дополнительные сведения об автоматных языках......214
S 14.1. Стандартные А-языки...........і .... 214 294
Оглавление
§ 14 2. Свойства стандартных А-языков............217
§ 14.3. Алгебраическое описание А-языков...........218
§ 14.4. Преобразования .................220
Глава XV. Дополнительные сведения о КС-языках..........232
§ 15 1. Языки Дика ...................232
§ 15.2. Стандартные КС-языки ... . . .......240
§ 15.3. Совпадение класса КС-языков с классом языков, допускаемых
автоматами с магазинной памятью .... .....244
§ 15.4 Упражнения ...................245
Глава XVI. Алгебраические языки................247
