Теория формальных языков
Учебное пособие

Эта страница посвящена книге 2004 года. Более полное изложение того же материала можно найти в книге "Математическая теория формальных языков", вышедшей двумя годами позже.

Материалы на этом сайте

• Учебное пособие
  • Полный текст (80 страниц): pdf (533 кб), PostScript.zip (308 кб)
  • Выходные сведения
  • Аннотация
  • Введение
  • Литература
  • Оглавление
• Дополнительные файлы
  • Схема зависимости параграфов: gif, PostScript, pdf
  • Список опечаток

Теория формальных языков

Выходные сведения

Пентус А. Е., Пентус М. Р.
Теория формальных языков: Учебное пособие. -- М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004. -- 80 с.

Аннотация

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

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

Введение

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

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

Многие определения и результаты пояснены простыми примерами. Из примера, приведённого сразу после леммы или теоремы, часто можно понять идею доказательства.

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

Литература

• Ахо А., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2001. -- 768 с.
• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. -- 612 с.
• Братчиков И. Л. Синтаксис языков программирования. М.: Мир, 1975. -- 232 с.
• Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. -- 326 с.
• Гладкий А. В. Формальные грамматики и языки. М.: Наука, 1973. -- 368 с.
• Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. М.: Наука, 1969. -- 192 с.
• Гордеев А. В., Молчанов А. Ю. Системное программное обеспечение. СПб.: Питер, 2001. -- 736 с.
• Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971. -- 294 с.
• Кук Д., Бейз Г. Компьютерная математика. М.: Наука, 1990. -- 384 с.
• Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985. -- 440 с.
• Логический подход к искусственному интеллекту: От классической логики к логическому программированию. М.: Мир, 1990. -- 432 с.
• Рейуорд-Смит В. Дж. Теория формальных языков. Вводный курс. М.: Радио и связь, 1988. -- 128 с.
• Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986. -- 159 с.
• Соколов В. А., Кушниренко О. Б., Бадин Н. М. Формальные языки и грамматики. Задачи и упражнения. Ярославль: Ярославский государственный университет, 1993. -- 55 с.
• Трахтенброт Б. А., Барздинь Я. М. Конечные автоматы (поведение и синтез). М.: Наука, 1970. -- 400 с.
• Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. -- 528 с.
• Lewis H. R., Papadimitriou C. H. Elements of the Theory of Computation. Prentice Hall, 1981. -- 466 p.
• Lewis H. R., Papadimitriou C. H. Elements of the Theory of Computation. 2nd ed. Prentice Hall, 1998. -- 361 p.
• Sipser M. Introduction to the Theory of Computation. PWS Publishing company, 1997. -- 396 p.

Оглавление

Звёздочками помечены факультативные разделы.

1.  Слова, языки и грамматики
  1.1.   Формальные языки
  1.2.   Гомоморфизмы
  1.3.   Порождающие грамматики
  1.4.   Классы грамматик

2.  Конечные автоматы
  2.1.   Недетерминированные конечные автоматы
  2.2*.  Конфигурации конечного автомата
  2.3.   Конечные автоматы с однобуквенными переходами
  2.4.   Характеризация праволинейных языков
  2.5*.  Нормальная форма праволинейных грамматик
  2.6.   Детерминированные конечные автоматы

3.  Основные свойства автоматных языков
  3.1.   Свойства замкнутости класса автоматных языков
  3.2.   Пересечение и дополнение автоматных языков
  3.3.   Лемма о разрастании для автоматных языков
  3.4.   Примеры неавтоматных языков

4.  Дополнительные свойства автоматных языков
  4.1.   Гомоморфизмы и автоматные языки
  4.2*.  Длины слов в автоматных языках

5.  Регулярные выражения
  5.1.   Определение регулярного выражения
  5.2*.  Свойства регулярных выражений
  5.3.   Теорема Клини

6.  Синтаксические моноиды
  6.1.   Множества правых контекстов
  6.2.   Минимизация детерминированных конечных автоматов
  6.3.   Множества двусторонних контекстов

7.  Неоднозначность в контекстно-свободных грамматиках
  7.1.   Деревья вывода
  7.2.   Однозначные контекстно-свободные грамматики
  7.3*.  Однозначные праволинейные грамматики
  7.4.   Языки Дика и Лукасевича

8.  Нормальные формы контекстно-свободных грамматик
  8.1.   Устранение бесполезных символов
  8.2.   Устранение ε-правил
  8.3.   Нормальная форма Хомского
  8.4*.  Нормальная форма Грейбах

9.  Основные свойства контекстно-свободных языков
  9.1.   Лемма о разрастании для контекстно-свободных языков
  9.2.   Свойства замкнутости класса линейных языков
  9.3.   Свойства замкнутости класса контекстно-свободных языков
  9.4.   Пересечение и дополнение контекстно-свободных языков
  9.5.   Пересечение контекстно-свободного языка с автоматным языком
  9.6*.  Теорема Парика

10. Автоматы с магазинной памятью
  10.1.  Определение автомата с магазинной памятью
  10.2.  Характеризация контекстно-свободных языков
  10.3*. Автоматы с магазинной памятью с однобуквенными переходами

11. Дополнительные свойства контекстно-свободных языков
  11.1*. Деление контекстно-свободных языков
  11.2.  Гомоморфизмы и контекстно-свободные языки
  11.3*. Представления контекстно-свободных языков посредством гомоморфизмов

12. Детерминированные контекстно-свободные языки
  12.1.  Детерминированные автоматы с магазинной памятью
  12.2*. Свойства класса детерминированных контекстно-свободных языков

13. Алгоритмические проблемы
  13.1.  Машины Тьюринга
  13.2.  Массовые задачи
  13.3*. Грамматики типа 0
  13.4.  Проблема соответствий Поста

14. Алгоритмически разрешимые проблемы
  14.1.  Неукорачивающие грамматики
  14.2*. Линейно ограниченные автоматы
  14.3.  Проблема выводимости слова
  14.4.  Проблема пустоты языка
  14.5.  Проблема бесконечности языка
  14.6.  Проблема равенства автоматных языков

15. Алгоритмически неразрешимые проблемы
  15.1.  Пересечение контекстно-свободных языков
  15.2.  Проблема однозначности
  15.3.  Дополнение контекстно-свободного языка
  15.4.  Проблема автоматности
  15.5.  Проблемы контекстно-свободности

Адрес: http://lpcs.math.msu.su/~pentus/tfyaw.htm Изменения внесены 12.08.2004. Анна Пентус, Мати Пентус Телефон/факс: + 7 - 495 - 939 30 31