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

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

• 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 канадских долларов)

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