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

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

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

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

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

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

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

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

8. Грамматики надстройки деревьев (tree-adjoining grammars). Многокомпонентные грамматики. Логика первого порядка над позициями в строке.