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

Общая литература к курсу:

• J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 1979. <small>(основы теории формальных языков; читать стоит только это издание: издание начала 2000-х значительно хуже)</small>
• M. A. Harrison, Introduction to Formal Language Theory, 1978. <small>(читается не очень легко, но зато описаны алгоритмы разбора и всё тщательно доказано)</small>
• A. Okhotin, &#147Nine open problems on conjunctive and Boolean grammars&#148, TUCS TR 794, 2006. <small>(обзор конъюнктивных и булевых грамматик, уже несколько устаревший: см. список решённых задач и дополнение к обзору)</small>
• Какое-то подобие конспектов лекций: http://users.utu.fi/aleokh/formal_grammars_wroclaw/.

Задачи для получения оценки за курс:

<small>(на тройку надо полностью решить две из пяти задач, на четвёрку --- три, на пятёрку --- четыре)</small>

• 1. Построить бесконтекстную грамматику для языка $L={a^{k_1}b \ldots a^{k_\ell}b \mid \ell \geqslant 1, \; k_i \geqslant 0, \; \exists i: k_i=i}$. Показать, что построенная грамматика неоднозначна.
• 2. Построить однозначную булеву грамматику для языка $L$ из первой задачи.
• 3. Показать, что если языки $K$ и $L$ над алфавитом ${a, b}$ --- линейные конъюнктивные (т.е., представимы конъюнктивной грамматикой с правилами вида $A \to u_1 B_1 v_1 & \ldots & u_n B_n v_n$ и $A \to w$), то язык $KcL$ (где $c$ --- дополнительный символ) --- тоже линейный конъюнктивный.
• 4. Для произвольной булевой грамматики $G$ построить алгоритм, который, получив на входе строку $w$, будет определять, порождает ли $G$ хотя бы один из циклических сдвигов строки $w$. Время работы алгоритма должно быть не более чем кубическим от длины $w$. <small>(на пятёрку с плюсом: быстрее, чем кубическим) (на четвёрку сойдёт время $n^{3.81}$, для этого нетрудно приспособить готовый алгоритм из лекций) (замечание: замкнуты ли булевы грамматики относительно циклического сдвига --- неизвестно)</small>
• 5. Доказать, что для конъюнктивных грамматик неразрешима следующая задача: по данной конъюнктивной грамматике над алфавитом ${a, b}$ определить, порождает ли она в точности язык ${a^n b^n | n \geqslant 0}$, или же какой-то иной язык. <small>(на четвёрку --- то же самое для языка ${\epsilon}$).</small>

Примеры задач для дальнейших исследований

<small>(уровня хорошей дипломной работы или неплохой статьи, написанной аспирантом)</small>

• Рассмотреть LL(k) линейные булевы грамматики и проверить, могут ли они задать какой-либо язык, не представимый булевой формулой над LL(1) линейными бесконтекстными языками. (предположительно, нет)
• Научиться строить однозначные конъюнктивные грамматики над однобуквенным алфавитом для широких классов языков. Для этого надо сперва обстоятельно изучить существующие теоремы о построении неоднозначных конъюнктивных грамматик (Еж, DLT 2007; Еж и Охотин, CSR 2007, STACS 2008).
• Рассмотреть магазинные автоматы с явными метками (visibly pushdown automata, Алур и Мадхусудан, 2004) и научиться преобразовывать их к линейным конъюнктивным грамматикам.

Большая практическая задача

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

Большие теоретические задачи (за каждую определена награда в 360 канадских долларов)

• Научиться доказывать для некоторых языков, что эти языки не порождаются никакой булевой грамматикой.
• Определить, замкнуты ли конъюнктивные языки относительно дополнения.