Математическая теория грамматик

Формальные грамматики и языки

Формальные языки. Порождающие грамматики. Языки, порождаемые грамматиками. Применение грамматик для описания фрагментов естественного языка.

Совпадение класса языков, порождаемых грамматиками, с классом перечислимых множеств. Теорема Райса о несуществовании нетривиальных разрешимых свойств языков, порождаемых грамматиками.

Иерархия Хомского. Контекстные, контекстно-свободные, автоматные (праволинейные) грамматики и языки.

Неукорачивающие грамматики. Алгоритм построения по неукорачивающей грамматике эквивалентной ей контекстной грамматики. Свойства класса контекстных языков. Примеры перечислимых языков, не являющихся контекстными.

Конечные автоматы и регулярные множества

Конечные автоматы Мура, недетерминированные автоматы, автоматы с частично определёнными функциями переходов. Задание конечных автоматов диаграммами. Множества, распознаваемые автоматами каждого из перечисленных типов.

Канонические праволинейные грамматики. Алгоритм построения по праволинейной грамматике эквивалентной ей канонической праволинейной грамматики. Алгоритм построения по канонической праволинейной грамматике конечного автомата, допускающего порождаемое этой грамматикой множество. Алгоритм построения по конечному автомату праволинейной грамматики, порождающей допускаемое этим автоматом множество.

Операции над множествами слов: конкатенация, итерация. Регулярные множества слов. Регулярные выражения. Теорема Клини о совпадении класса множеств, допускаемых конечными автоматами, с классом регулярных множеств.

Лемма-насос для автоматных языков. Свойства замкнутости класса автоматных языков. Примеры линейных языков, не являющихся автоматными.

Синтаксические моноиды.

Линейные языки

Линейные грамматики и языки. Канонические линейные грамматики. Свойства класса линейных языков. Примеры контекстно-свободных языков, не являющихся линейными.

Контекстно-свободные языки и автоматы с магазинной памятью

Канонические контекстно-свободные грамматики в форме Хомского и в форме Грейбах.

Деревья вывода и левосторонние выводы. Неоднозначные грамматики. Существенно неоднозначные языки.

Автоматы с магазинной памятью. Алгоритм построения по контекстно-свободной грамматике автомата с магазинной памятью, допускающего порождаемое этой грамматикой множество. Алгоритм построения по автомату с магазинной памятью контекстно-свободной грамматики, порождающей допускаемое этим автоматом множество.

Лемма-насос для контекстно-свободных языков. Свойства замкнутости класса контекстно-свободных языков. Примеры контекстных языков, не являющихся контекстно-свободными.

Контекстно-свободность пересечения контекстно-свободного языка и автоматного языка.

Постовские системы соответствия

Полутуэвская продукция, система. Проблема слов для полутуэвской системы. Сведение проблемы остановки к проблеме слов некоторой полутуэвской системы. Существование полутуэвской системы с неразрешимой проблемой слов.

Постовская система соответствия, решение этой системы. Построение по полутуэвской системе S и паре p слов над ее алфавитом постовской системы соответствия, имеющей решение тогда и только тогда, когда в S выводима p . Неразрешимость проблемы распознавания существования решения постовской системы соответствия.

Алгоритмические проблемы, связанные с порождающими грамматиками

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

Построение по постовской системе P соответствия пары контекстно-свободных языков, тогда и только тогда имеющих непустое пересечение, когда P имеет решение. Нераспознаваемость в классе контекстно-свободных грамматик проблемы непустоты пересечения языков, проблемы бесконечности пересечения языков, проблемы полноты языка, проблемы равенства языков, проблемы бесконечности дополнения языка, проблемы автоматности языка, проблемы контекстно-свободности пересечения языков, проблемы контекстно-свободности

дополнения языка. Нераспознаваемость проблемы неоднозначности контекстно-свободной грамматики.

Сложность вычисления и сложность описания

Меры сложности вычислений. Существование сколь угодно сложно вычислимых функций. Теорема об ускорении. Классы сложности. Теорема о пробелах.

Алгоритмический подход к понятию количества информации. Сложность конечного объекта. Теорема Колмогорова о существовании оптимального способа описания.

Полиномиальные алгоритмы и класс P. Недетерминированные вычисления и класс NP. Понятие NP-полной задачи. NP-полнота задач о выполнимости, о существовании гамильтонова цикла, о коммивояжёре, о разбиении.

Категориальные грамматики

Базисные категориальные грамматики. Исчисление Айдукевича--Бар-Хиллела. Описание фрагмента английского языка с помощью категориальной грамматики.

Исчисление Ламбека

Синтаксическое исчисление Ламбека, примеры выводов в нём. Категориальные грамматики Ламбека. Теоремы об устранимости сечения, об интерполяционном свойстве исчисления Ламбека. Интерпретация исчисления Ламбека в полугруппе подмножеств свободной полугруппы, теорема о корректности, теорема о полноте исчисления Ламбека. Интерпретация исчисления Ламбека в свободной группе.

Теорема о совпадении класса контекстно-свободных языков с классом языков, распознаваемых грамматиками Ламбека.

Семантика Монтегю

Язык интенсиональной логики, его интерпретации. Временные и модальные логики первого порядка. Принцип лямбда-конверсии в интенсиональной логике.

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

Литература

• Теория и реализация языков программирования (соавт. Галочкин М. П., Гончар Д. Р., Фуругян М. Г.) — М.: МЗ-Пресс, 2006. 350 с. (2-е изд., испр. и доп.). ISBN 5-94073-094-9
• Мартыненко Б.К. Языки и трансляции: учеб. пос. СПб.ГУ, 2002 г. (ранее было разм. на странице автора на портале СПб.ГУ).
• Шень А. Х. Программирование: теоремы и задачи. М.: МЦНМО, 2004. (разм. на портале МЦНМО с разр. автора) – здесь можно посмотреть алгоритм Кнута-Морриса-Пратта.