Home   Papers   Teaching   CV   Leisure

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

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

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


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

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

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

Аннотация

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

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

Введение

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

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

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

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

Литература

Оглавление

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

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.  Проблемы контекстно-свободности
Home   Papers   Teaching   CV   Leisure
 
MPАдрес: http://lpcs.math.msu.su/~pentus/tfyaw.htm
Изменения внесены 12.08.2004.
Анна Пентус, Мати Пентус
Телефон/факс: + 7 - 495 - 939 30 31