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

Курс «Формальные грамматики»: сентябрь 2014 г., 15 лекций, лектор: Александр Охотин (университет Турку, Финляндия).

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

Приветствуются любые замечания по содержанию материалов к лекциям: если что-то неправильно или плохо понятно, то, пожалуйста, напишите, что именно.

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

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

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

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

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

Файл:Formal grammars 2014 lectures 2 3 4.pdf (редакция от 16 сентября, добавлены все недостающие разделы)

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

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

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

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

Лекция 5: Конъюнктивные грамматики

Определения конъюнктивных грамматик через логический вывод, перезапись термов, деревья разбора и языковые уравнения. Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. Приведение к нормальному виду Хомского. Понятие о булевых грамматиках. (11 сентября)

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

Лекция 6: Однозначные грамматики

Неоднозначность в естественных языках и языках программирования. Комбинаторные и аналитические методы доказательства существенной неоднозначности. (11 сентября)

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

Лекция 7: Линейные грамматики

Обыкновенные линейные грамматики, лемма накачки для них. Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность. Лемма Терье. (12 сентября)

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

Лекция 8: Многокомпонентные грамматики, логика FO(LFP)

Грамматики обёртывания пар и грамматики надстройки деревьев (tree-adjoining grammars). Логика первого порядка над позициями в строке FO(LFP), представление грамматик в этой логике. Алгоритм проверки истинности формул логики FO(LFP) как прототип алгоритмов синтаксического анализа. (12 сентября)

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

Лекция 9: Табличные алгоритмы синтаксического анализа

Алгоритм Кокка-Касами-Янгера. Использование умножения матриц для ускорения алгоритма. Умножение матриц по методу Штрассена и по методу Арлазарова и др. (22 сентября)

Файл:Formal grammars 2014 lectures 9 10.pdf (редакция от 30 сентября)

Лекция 10: Табличные алгоритмы синтаксического анализа (окончание)

Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время. Разбор для грамматик обёртывания пар. (22 сентября)

Лекция 11: Разбор сверху вниз

LL(k) анализ для обыкновенных грамматик, рекурсивный спуск. Удаление пустых правил из LL-грамматик. Языки, не представимые LL-грамматиками. Теорема Розенкранца--Стирнса о регулярном объединении LL-языков. (22 сентября)

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

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

Анализ через сдвиг и свёртку. Детерминированный конечный автомат, читающий стек. Класс LR(k) грамматик. Построение таблиц по методу SLR(k). Магазинные автоматы и их равносильность LR(k) грамматикам. (24 сентября)

Файл:Formal grammars 2014 lectures 12 13.pdf (весьма неполная редакция от 25 сентября)

Лекция 13: Автоматы, управляемые входом; обобщённый LR

Автоматы, управляемые входом (input-driven automata; visibly pushdown automata). Равносильность их детерминированных и недетерминированных разновидностей. Грамматики, управляемые входом. Обобщённый LR: пример работы, оценки сложности. (24 сентября)

Лекция 14: Вычислительная сложность разбора

Разбор обыкновенных грамматик с использованием памяти $(\log n)^{2}$, разбор схемой высоты $(\log n)^{2}$. Линейная грамматика для NLOGSPACE-полного языка. Задача принадлежности данной строки данной обыкновенной грамматике и её P-полнота. Равносильность грамматик 1-го порядка классу P. (24 сентября)

Файл:Formal grammars 2014 lecture 14.pdf (редакция от 2 октября)

Лекция 15: Разрешимость свойств грамматик

Язык вычислений машины Тьюринга (VALC) и его представление в виде пересечения двух LL(1) линейных языков. Неразрешимость основных свойств линейных грамматик. Разрешимость проверки равносильности LL(k) грамматик. Разрешимость задачи включения для автоматов, управляемых входом. Иерархия семейств грамматик. (26 сентября)

Файл:Formal grammars 2014 lecture 15.pdf (редакция от 30 сентября)

Упражнения

Задание 1: к 22 сентября

1. Построить обыкновенную грамматику для языка всех палиндромов: $L_{1}=\{w\in \{a,b\}^{*}\mid w=w^{R}\}$. Показать, как строка $ababa$ выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности $\varphi ^{k}(\bot )$.
2. Доказать, что не существует обыкновенной грамматики для языка $L_{2}=\{a^{k_{1}}b\ldots a^{k_{n}}b\mid n\geqslant 1,0\leqslant k_{1}\leqslant \ldots \leqslant k_{n}\}$
3. Построить конъюнктивную грамматику для языка $L_{2}$.
4. Построить однозначную обыкновенную грамматику для языка $L_{3}=\{c^{m}a^{\ell _{0}}b\ldots a^{\ell _{m-1}}ba^{\ell _{m}}b\ldots a^{\ell _{z}}bd^{n}\mid m,n,\ell _{i}\geqslant 0,z\geqslant 1,\ell _{m}=n\}$
5. Является ли язык $L_{3}$ линейным конъюнктивным?
6. Пусть $D=\{\varepsilon ,ab,aabb,abab,aaabbb,\ldots \}$ --- язык Дика над алфавитом $\{a,b\}$. Существует ли грамматика обёртывания пар для языка $L_{4}=\{wc^{|w|}\mid w\in D\}=\{\varepsilon ,abcc,aabbcccc,ababcccc,aaabbbcccccc,\ldots \}$?
7. Построить грамматику 1-го порядка для языка $\{ww\mid w\in \{a,b\}^{*}\}$.

Файл:Formal grammars 2014 homework 1 solutions.pdf

(проверенные работы переданы на кафедру)

Задание 2: к 13 октября

1. Постоить обыкновенную грамматику в нормальном виде Хомского для языка Дика $D=\{\varepsilon ,ab,aabb,abab,aaabbb,\ldots \}$ над алфавитом $\{a,b\}$. Для этой грамматики и для входной строки $w=abaabba\notin D$, построить таблицу разбора $T_{i,j}$, как в алгоритме Кокка–Касами–Янгера.
2. Рассмотреть работу алгоритма Валианта (синтаксический анализ через умножение матриц, лекции 9-10) для грамматики, построенной в прошлом упражнении. Среди всех действий, производимых алгоритмом, найти то произведение булевых матриц, после вычисления которого станет верным условие $S\in f(P_{0,6})$, где $S$ — начальный символ грамматики. Описать, когда и как именно вычисляется это произведение — то есть, какая процедура, вызванная с какими значениями, и какой оператор в ней умножает какие две булевы матрицы какого размера, каков результат умножения, и какие элементы $P_{i,j}$ будут этим затронуты?
3. Замкнут ли класс LL языков относительно пересечения с регулярными языками? Если замкнут, привести построение (см. построение такого рода для всего класса обыкновенных грамматик в материалах к лекциям 2-4), а если незамкнут, привести пример LL грамматики и регулярного языка с доказательством несуществования LL грамматики для их пересечения (см. доказательства такого рода в материалах к лекции 11).
4. Построить линейную грамматику для языка $f(L_{0})$, где $L_{0}=\{w\$w^{R}\mid w\in \{a,b\}^{*}\}$ и $f(L)=\{[w_{1,1}\#\ldots \#w_{1,k_{1}}]\ldots [w_{m,1}\#\ldots \#w_{m,k_{m}}]\mid \exists i_{1},\ldots ,i_{m}:\;w_{1,i_{1}}w_{2,i_{2}}\ldots w_{m,i_{m}}\in L\}$ (это NLOGSPACE-полный язык, приведённый на лекции).
5. Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку чётной длины»? Если разрешима, привести алгоритм, а если неразрешима, доказать это с помощью методов лекции 15 (использовав язык VALC в готовом виде, или же определив новый его вариант).
6. Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку-палиндром $w$, т.е., строку, для которой $w=w^{R}$»?
7. Для произвольной данной линейной грамматики G, пусть $L=\{vu\mid uv\in L(G)\}$ — циклический сдвиг порождаемого ею языка. Построить алгоритм, определяющий принадлежность данной на входе строки языку $L$, и использующий как можно меньше памяти. Объём памяти считать функцией $s(n)$, где $n$ — длина входной строки, и этот объём должен быть по крайней мере меньше, чем линейным. Примечания: алгоритм строится по грамматике, и потому зависимостью требуемого объёма памяти от размера этой грамматики можно пренебречь; алгоритм должен быть детерминированным; если получится использовать алгоритмы, приведённые на лекциях, то их можно не повторять, но нужно указать, как именно и к чему именно они применяются.

(задания принимаются по эл. почте в формате pdf, печатном или отсканированном рукописном; отсканированные файлы должны быть пригодны для печати и умещаться в один мегабайт)

(получены работы Е. Акимова, К. Б. Аманова, А. Афанасьева, П. Авдеева, Т. Бондарева, Б. Бугаева, С. Ворончихина, К. Елагина, И. Гайдая, И. В. Гончаровой, Д. Жаркова, А. В. Калакуцкого, Н. Карташова, А. Лиозновой, А. Маловой, Т. С. Малыгиной, Д. Мелешко, К. Новокрещенова, Н. Обедина, А. Ордияна, С. Сидорова, Н. К. Ситдыковой, Е. Старостиной, М. Тураева, Т. Тураева, Е. Устюжаниной, М. Хабибуллина, А. Цветкова, П. Чуприкова, О. Яснева)