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

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

• Полный текст (в формате HTML, по разделам)

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

• Учебное пособие
  • Выходные сведения
  • Аннотация
  • Оглавление
• Дополнительные файлы
  • Список опечаток

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

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

Пентус А. Е., Пентус М. Р.
Математическая теория формальных языков: Учебное пособие. — М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 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.  Проблемы контекстной свободности

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