В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом.
Имеется большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги.
Книга окажется полезной математику, желающему ознакомиться с теорией формальных грамматик и ее связями с другими математическими теориями.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода............. 5
Предисловие автора................... 8
Предварительные сведения................ 12
Глава 1. контекстно-свободные языки и языки типа алгол.................. 19
1.1. Языки, порождаемые грамматиками.... 19
1.2. Языки типа АЛГОЛ............ 27
1.3. Эквивалентность КС-языков и языков типа АЛГОЛ................. 30
1.4. Вспомогательные утверждения....... 35
1.5. Деревья выводов............. 41
1.6. Неопределенность............. 49
1.7. Подстановка............... 57
1.8. Неукорачивающие КС-грамматики..... 59
1.9. Историческая справка........... 70
Глава 2. автоматы и языки............. 71
2.1. Конечные автоматы и регулярные множества...... 71
2.2. Линейные правила............ 78
2.3. КС-языки специального вида....... 83
2.4. Автоматы с магазинной памятью...... 89
2.5. Характеристика КС-языков в терминах МП-автоматов................ 94
2.6. Детерминированные КС-языки....... 108
2.7. Историческая справка........... 119
Глава 3. операции над кс-языками........ 120
3.1. Языки, не являющиеся контекстно-свободными......... .......... 120
3.2. Пересечение и разность.......... 126
3.3. Последовательностные преобразования ... 130
3.4. Характеристика конечного преобразования......... 140
3.5. Преобразователи с магазинной памятью....... 146
3.6. Некоторые специальные операции..... 151
3.7. Нормальная форма КС-языка....... 157
3.8. Историческая справка........... 163
Глава 4. алгоритмические проблемы...... 165
4.1. Алгоритмически разрешимые проблемы... 166
4.2. Основные алгоритмически неразрешимые проблемы.................. 170
4.3. Алгоритмические проблемы, связанные с конечными преобразованиями........ 185
4.4. Алгоритмические проблемы, связанные с МП-преобразователями.......... 194
4.5. Неразрешимость проблемы распознавания определенности КС-грамматики....... 196
4.6. Историческая справка........... 199
Глава 5. ограниченные кс-языки........ 200
5.1. Основные понятия............ 200
5.2. Теорема Парика............. 206
5.3. Структура ограниченных КС-языков.... 212
5.4. Характеристики ограниченных КС-языков..... 223
5.5. Распознавание ограниченности КС-языка.. 239
5.6. Другие алгоритмические проблемы..... 249
5.7. Историческая справка........... 260
Глава 6. существенная неопределенность.... 261
6.1. Существенно неопределенные КС-языки, содержащиеся во множестве а*... an.... 261
6.2. Ограниченные существенно неопределенные КС-языки..
Дополнительно: Почти всегда можно ЗАБРАТЬ СРАЗУ в день заказа! м.Беляево, Дмитровская. Также отправляю ПОЧТОЙ СРАЗУ.
В ПОДАРОК - книги с ценой до 140 р на 30% от заказа
Почти все книги НОВЫЕ, продаю большую домашнюю библиотеку
ЗАБРАТЬ МОЖНО: 1. м.Беляево 2.м.Дмитровская 3. Метро в ЦЕНТРЕ, Курская 4. ДОСТАВКА 5. ПОЧТОЙ, СДЭК и т.п. отправляю СРАЗУ после заказа, по тарифам почты, упакую в картон, отправлю... [подробнее]
)
как новое;
В продаже с 19.09.2024
