Формальные грамматики 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\}^{*}\}$.

(почти всё проверено, скоро будут результаты)

Задание 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, печатном или отсканированном рукописном; отсканированные файлы должны быть пригодны для печати и умещаться в один мегабайт)