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

Введение......13Глава 1. Слова, языки и грамматики......161.1. Формальные языки......161.2. Операции над языками......191.3. Гомоморфизмы......221.4. Порождающие грамматики......231.5. Классы грамматик......27Глава 2. Конечные автоматы......322.1. Недетерминированные конечные автоматы......332.2. Конфигурации конечного автомата......372.3. Конечные автоматы с однобуквенными переходами......392.4. Характеризация праволинейных языков......412.5. Нормальная форма праволинейных грамматик......432.6. Детерминированные конечные автоматы......442.7. Преобразование конечного автомата к детерминированному виду......46Глава 3. Основные свойства автоматных языков......493.1. Свойства замкнутости класса автоматных языков......493.2. Пересечение и дополнение автоматных языков......523.3. Лемма о разрастании для автоматных языков......543.4. Примеры неавтоматных языков......56Глава 4. Дополнительные свойства автоматных языков......584.1. Гомоморфизмы и автоматные языки......584.2. Локальные языки......594.3. Длины слов в автоматных языках......61Глава 5. Регулярные выражения......635.1.Определение регулярного выражения......635.2. Свойства регулярных выражений......655.3. Теорема Клини......675.4. Звёздная высота......71Глава 6. Синтаксические моноиды......736.1. Множества правых контекстов......736.2. Минимизация детерминированных конечных автоматов......776.3. Множества двусторонних контекстов......806.4.Классы эквивалентности слов......82Глава 7. Неоднозначность в контекстно-свободных грамматиках......867.1. Деревья вывода......867.2. Однозначные контекстно-свободные грамматики......887.3. Однозначные праволинейные грамматики......917.4. Языки Дика и Лукасевича......92Глава 8. Нормальные формы контекстно-свободных грамматик......968.1. Устранение бесполезных символов......968.2. Устранение эпсилон-правил......988.3. Нормальная форма Хомского......998.4. Нормальная форма Грейбах......101Глава 9. Основные свойства контекстно-свободных языков......1069.1. Лемма о разрастании для контекстно-свободных языков......1069.2. Лемма о разрастании для линейных языков......1099.3. Свойства замкнутости класса линейных языков......1109.4. Свойства замкнутости класса контекстно-свободных языков......1129.5. Пересечение и дополнение контекстно-свободных языков......1139.6. Пересечение контекстно-свободного языка с автоматным языком......1149.7. Теорема Парика......117Глава 10. Автоматы с магазинной памятью......12010.1. Определение автомата с магазинной памятью......12010.2. Характеризация контекстно-свободных языков......12510.3. Автоматы с магазинной памятью с однобуквенными переходами......129Глава 11. Дополнительные свойства контекстно-свободных языков......13211.1. Деление контекстно-свободных языков......13211.2. Гомоморфизмы и контекстно-свободные языки......13411.3. Представления контекстно-свободных языков посредством гомоморфизмов......139Глава 12. Детерминированные контекстно-свободные языки......14212.1. Детерминированные автоматы с магазинной памятью......14212.2. Свойства класса детерминированных контекстно-свободных языков......144Глава 13. Синтаксический разбор......14913.1. Нисходящий разбор......14913.2. Восходящий разбор......164Глава 14. Алгоритмические проблемы......16914.1. Машины Тьюринга......16914.2. Разрешимые и перечислимые множества......17614.3. Массовые задачи......17914.4. Грамматики типа 0......18114.5. Проблема соответствий Поста......183Глава 15. Алгоритмически разрешимые проблемы......18615.1. Неукорачивающие грамматики......18615.2. Линейно ограниченные автоматы......18715.3. Проблема выводимости слова......18815.4. Проблема пустоты языка......18915.5. Проблема бесконечности языка......19015.6. Проблема эквивалентности конечных автоматов......19115.7. Проблема эквивалентности детерминированных МП-автоматов......19215.8. Классы P и NP......19215.9. Проблема неравенства регулярных выражений без итерации......194Глава 16. Алгоритмически неразрешимые проблемы......19816.1. Пересечение контекстно-свободных языков......19816.2. Проблема однозначности......20116.3. Дополнение контекстно-свободного языка......20216.4. Проблема автоматности......20416.5. Проблемы контекстной свободности......206Ответы к упражнениям......210Список литературы......236Предметный указатель......240