URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Гинзбург С. Математическая теория контекстно-свободных языков: Пер. с англ.
Id: 3864
 
1699 руб.

Математическая теория контекстно-свободных языков: Пер. с англ.

1970. 328 с. Твердый переплет. Букинист. Состояние: 4. .

 Аннотация

В книге достаточно полно изложены основные понятия и результаты теории контекстно-свободных грамматик и языков, прослеживаются ее связи с теорией автоматов, языками программирования, лингвистикой и машинным переводом. Имеется большое число упражнений самой различной трудности, которые в совокупности существенно дополняют основной текст книги.

Книга окажется полезной математику, желающему детально ознакомиться с теорией формальных грамматик и ее связями с другими математическими теориями.


 ОГЛАВЛЕНИЕ

Предисловие редактора перевода............. 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. Ограниченные существенно неопределенные КС-языки................. 278

6.3. Алгоритмическая неразрешимость проблемы распознавания существенной неопределенности.................... 295

6.4. Историческая справка........... 300

Приложение................... 301

Библиография.................. 310

Предметный указатель............ 320

 
© URSS 2016.

Информация о Продавце