Книга: Пентус А. Е., Пентус М. Р. «Математическая теория формальных языков»
|
|
Серия: "Основы информатики и математики" Учебник посвящен классическому разделу математической лингвистики и теоретической информатики - теории формальных языков. Рассматриваются порождающие грамматики, регулярные выражения, конечные автоматы, автоматы с магазинной памятью. Содержание:Введение...... 13 Глава 1. Слова, языки и грамматики...... 16 1. 1. Формальные языки...... 16 1. 2. Операции над языками...... 19 1. 3. Гомоморфизмы...... 22 1. 4. Порождающие грамматики...... 23 1. 5. Классы грамматик...... 27 Глава 2. Конечные автоматы...... 32 2. 1. Недетерминированные конечные автоматы...... 33 2. 2*. Конфигурации конечного автомата...... 37 2. 3. Конечные автоматы с однобуквенными переходами...... 39 2. 4. Характеризация праволинейных языков...... 41 2. 5*. Нормальная форма праволинейных грамматик...... 43 2. 6. Детерминированные конечные автоматы...... 44 2. 7. Преобразование конечного автомата к детерминированному виду...... 46 Глава 3. Основные свойства автоматных языков...... 49 3. 1. Свойства замкнутости класса автоматных языков...... 49 3. 2. Пересечение и дополнение автоматных языков...... 52 3. 3. Лемма о разрастании для автоматных языков...... 54 3. 4. Примеры неавтоматных языков...... 56 Глава 4. Дополнительные свойства автоматных языков...... 58 4. 1. Гомоморфизмы и автоматные языки...... 58 4. 2*. Локальные языки...... 59 4. 3*. Длины слов в автоматных языках...... 61 Глава 5. Регулярные выражения...... 63 5. 1. Определение регулярного выражения...... 63 5. 2*. Свойства регулярных выражений...... 65 5. 3. Теорема Клини...... 67 5. 4*. Звёздная высота...... 71 Глава 6. Синтаксические моноиды...... 73 6. 1. Множества правых контекстов...... 73 6. 2. Минимизация детерминированных конечных автоматов...... 77 6. 3. Множества двусторонних контекстов...... 80 6. 4*. Классы эквивалентности слов...... 82 Глава 7. Неоднозначность в контекстно-свободных грамматиках...... 86 7. 1. Деревья вывода...... 86 7. 2. Однозначные контекстно-свободные грамматики...... 88 7. 3*. Однозначные праволинейные грамматики...... 91 7. 4. Языки Дика и Лукасевича...... 92 Глава 8. Нормальные формы контекстно-свободных грамматик...... 96 8. 1. Устранение бесполезных символов...... 96 8. 2. Устранение эпсилон-правил...... 98 8. 3. Нормальная форма Хомского...... 99 8. 4*. Нормальная форма Грейбах...... 101 Глава 9. Основные свойства контекстно-свободных языков...... 106 9. 1. Лемма о разрастании для контекстно-свободных языков...... 106 9. 2*. Лемма о разрастании для линейных языков...... 109 9. 3. Свойства замкнутости класса линейных языков...... 110 9. 4. Свойства замкнутости класса контекстно-свободных языков...... 112 9. 5. Пересечение и дополнение контекстно-свободных языков...... 113 9. 6. Пересечение контекстно-свободного языка с автоматным языком...... 114 9. 7*. Теорема Парика...... 117 Глава 10. Автоматы с магазинной памятью...... 120 10. 1. Определение автомата с магазинной памятью...... 120 10. 2. Характеризация контекстно-свободных языков...... 125 10. 3*. Автоматы с магазинной памятью с однобуквенными переходами...... 129 Глава 11. Дополнительные свойства контекстно-свободных языков...... 132 11. 1*. Деление контекстно-свободных языков...... 132 11. 2. Гомоморфизмы и контекстно-свободные языки...... 134 11. 3*. Представления контекстно-свободных языков посредством гомоморфизмов...... 139 Глава 12. Детерминированные контекстно-свободные языки...... 142 12. 1. Детерминированные автоматы с магазинной памятью...... 142 12. 2*. Свойства класса детерминированных контекстно-свободных языков...... 144 Глава 13. Синтаксический разбор...... 149 13. 1. Нисходящий разбор...... 149 13. 2. Восходящий разбор...... 164 Глава 14. Алгоритмические проблемы...... 169 14. 1. Машины Тьюринга...... 169 14. 2. Разрешимые и перечислимые множества...... 176 14. 3. Массовые задачи...... 179 14. 4*. Грамматики типа 0...... 181 14. 5. Проблема соответствий Поста...... 183 Глава 15. Алгоритмически разрешимые проблемы...... 186 15. 1. Неукорачивающие грамматики...... 186 15. 2*. Линейно ограниченные автоматы...... 187 15. 3. Проблема выводимости слова...... 188 15. 4. Проблема пустоты языка...... 189 15. 5. Проблема бесконечности языка...... 190 15. 6. Проблема эквивалентности конечных автоматов...... 191 15. 7*. Проблема эквивалентности детерминированных МП-автоматов...... 192 15. 8*. Классы P и NP...... 192 15. 9*. Проблема неравенства регулярных выражений без итерации...... 194 Глава 16. Алгоритмически неразрешимые проблемы...... 198 16. 1. Пересечение контекстно-свободных языков...... 198 16. 2. Проблема однозначности...... 201 16. 3. Дополнение контекстно-свободного языка...... 202 16. 4. Проблема автоматности...... 204 16. 5. Проблемы контекстной свободности...... 206 Ответы к упражнениям...... 210 Список литературы...... 236 Предметный указатель...... 240 Издательство: "Интернет-Университет Информационных Технологий" (2006)
ISBN: 5955600620 |
См. также в других словарях:
МАТЕМАТИЧЕСКАЯ ЛИНГВИСТИКА — математическая дисциплина, предметом к рой является разработка и изучение понятий, образующих основу формального аппарата для описания строения естественных языков (т. е. метаязыка лингвистики). Возникновение М. л. можно отнести приблизительно к… … Математическая энциклопедия
Математическая лингвистика — математическая дисциплина, разрабатывающая формальный аппарат для описания строения естественных и некоторых искусственных языков. Возникла в 50 х годах 20 века в связи с назревшей в языкознании потребностью уточнения его основных понятий … Большая советская энциклопедия
МАТЕМАТИЧЕСКАЯ ЛОГИКА — один из ведущих разделов современной логики и математики. Сформировался в 19 20 ст. как реализация идеи о возможности записать все исходные допущения на языке знаков, аналогичных математическим и тем самым заменить рассуждения вычислениями.… … Новейший философский словарь
Математическая лингвистика — Математическая лингвистика математическая дисциплина, предметом которой является разработка формального аппарата для описания строения естественных и некоторых искусственных языков. Возникла в 50‑х гг. 20 в.; одним из главных стимулов появления… … Лингвистический энциклопедический словарь
Математическая логика — логика, развиваемая математическим методом. Характерным для М. л. является использование формальных языков с точным синтаксисом и чёткой семантикой, однозначно определяющими понимание формул. Потребность в такой логике выявилась в начале… … Большая советская энциклопедия
Автоматов теория — часть теоретической кибернетики (См. Кибернетика), объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50 х гг. 20 в. в связи с требованиями практики проектирования вычислительных… … Большая советская энциклопедия
