Формальные грамматики 2014 — различия между версиями

Версия 21:07, 9 сентября 2014

Содержание лекций

Лекция 1: Введение, регулярные языки

Математические модели синтаксиса. Формальные языки. Конечные автоматы и регулярные выражения, их равносильность. Примеры. Замкнутость относительно основных действий. Непредставимые множества.

Файл:Formal grammars 2014 lecture 1.pdf

Лекция 2: Обыкновенные грамматики

Обыкновенные формальные грамматики (в терминологии Хомского, "бесконтекстные"). Определения через перезапись строк, через деревья разбора, через логический вывод и через языковые уравнения. Равносильность определений. Примеры грамматик. Замкнутость относительно объединения, конкатенации, звёздочки, а также циклического сдвига.

Лекция 3: Свойства обыкновенных грамматик

Языки, не представимые обыкновенными грамматиками. Лемма накачки, лемма Огдена. Грамматики над односимвольным алфавитом. Нормальный вид Хомского.

Лекция 4: Представления обыкновенных грамматик

Нормальный вид Грейбах. Нормальный вид Розенкранца. Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. Теорема Грейбах о "самом сложном языке".

Конъюнктивные грамматики

Однозначные грамматики

Линейные грамматики

Многокомпонентные грамматики, логика FO(LFP)

Табличные алгоритмы синтаксического анализа

Рекурсивный спуск

LR(k) анализ и детерминированные языки

Оценки сложности синтаксического анализа

Разрешимость свойств грамматик