Home   Papers   Teaching   CV   Leisure

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

Материалы на других сайтах

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


Математическая теория формальных языков

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

Пентус А. Е., Пентус М. Р.
Математическая теория формальных языков: Учебное пособие. М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2006. 247 с.: ил. (Серия "Основы информатики и математики").

Аннотация

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

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

Оглавление

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

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

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

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

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

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

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

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.   Пересечение контекстно-свободного языка с автоматным языком
  9.7*.  Теорема Парика

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

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

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

13. Синтаксический разбор
  13.1.   Нисходящий разбор
  13.2.   Восходящий разбор

14. Алгоритмические проблемы
  14.1.  Машины Тьюринга
  14.2.  Разрешимые и перечислимые множества
  14.3.  Массовые задачи
  14.4*. Грамматики типа 0
  14.5.  Проблема соответствий Поста

15. Алгоритмически разрешимые проблемы
  15.1.  Неукорачивающие грамматики
  15.2*. Линейно ограниченные автоматы
  15.3.  Проблема выводимости слова
  15.4.  Проблема пустоты языка
  15.5.  Проблема бесконечности языка
  15.6.  Проблема эквивалентности конечных автоматов
  15.7.  Проблема эквивалентности детерминированных МП-автоматов
  15.8.  Классы P и NP
  15.9.  Проблема неравенства регулярных выражений без итерации

16. Алгоритмически неразрешимые проблемы
  16.1.  Пересечение контекстно-свободных языков
  16.2.  Проблема однозначности
  16.3.  Дополнение контекстно-свободного языка
  16.4.  Проблема автоматности
  16.5.  Проблемы контекстной свободности
Home   Papers   Teaching   CV   Leisure
 
MPАдрес: http://lpcs.math.msu.su/~pentus/mtfyaw.htm
Изменения внесены 19.10.2011.
Анна Пентус, Мати Пентус
Телефон/факс: + 7 - 495 - 939 30 31