Формальные грамматики 2014
Содержание
- 1 Содержание лекций
- 1.1 Введение, регулярные языки
- 1.2 Обыкновенные грамматики
- 1.3 Свойства обыкновенных грамматик
- 1.4 Представления обыкновенных грамматик
- 1.5 Конъюнктивные грамматики
- 1.6 Однозначные грамматики
- 1.7 Линейные грамматики
- 1.8 Многокомпонентные грамматики, логика FO(LFP)
- 1.9 Табличные алгоритмы синтаксического анализа
- 1.10 Рекурсивный спуск
- 1.11 LR(k) анализ и детерминированные языки
- 1.12 Оценки сложности синтаксического анализа
- 1.13 Разрешимость свойств грамматик
Содержание лекций
Введение, регулярные языки
Математические модели синтаксиса. Формальные языки. Конечные автоматы и регулярные выражения, их равносильность. Примеры. Замкнутость относительно основных действий. Непредставимые множества.
Обыкновенные грамматики
Обыкновенные формальные грамматики (в терминологии Хомского, "бесконтекстные"). Определения через перезапись строк, через деревья разбора, через логический вывод и через языковые уравнения. Равносильность определений. Примеры грамматик. Замкнутость относительно объединения, конкатенации, звёздочки, а также циклического сдвига.
Свойства обыкновенных грамматик
Языки, не представимые обыкновенными грамматиками. Лемма накачки, лемма Огдена. Грамматики над односимвольным алфавитом. Нормальный вид Хомского.
Представления обыкновенных грамматик
Нормальный вид Грейбах. Нормальный вид Розенкранца. Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. Теорема Грейбах о "самом сложном языке".
