Формальные грамматики 2014 — различия между версиями
Okhotin (обсуждение | вклад) (→Лекция 12: LR(k) анализ и детерминированные языки) |
м |
||
(не показано 28 промежуточных версий 1 участника) | |||
Строка 3: | Строка 3: | ||
== Содержание лекций == | == Содержание лекций == | ||
+ | |||
+ | Приветствуются любые замечания | ||
+ | по содержанию материалов к лекциям: | ||
+ | если что-то неправильно или плохо понятно, | ||
+ | то, пожалуйста, напишите, что именно. | ||
=== Лекция 1: Введение, регулярные языки === | === Лекция 1: Введение, регулярные языки === | ||
Строка 11: | Строка 16: | ||
Примеры. Замкнутость относительно основных действий. | Примеры. Замкнутость относительно основных действий. | ||
Нерегулярные языки. | Нерегулярные языки. | ||
+ | ''(8 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 1.pdf]] | [[Файл:Formal grammars 2014 lecture 1.pdf]] | ||
Строка 26: | Строка 32: | ||
Замкнутость относительно объединения, конкатенации, звёздочки, | Замкнутость относительно объединения, конкатенации, звёздочки, | ||
а также циклического сдвига. | а также циклического сдвига. | ||
+ | ''(8 сентября)'' | ||
[[Файл:Formal grammars 2014 lectures 2 3 4.pdf]] | [[Файл:Formal grammars 2014 lectures 2 3 4.pdf]] | ||
Строка 37: | Строка 44: | ||
Грамматики над односимвольным алфавитом. | Грамматики над односимвольным алфавитом. | ||
Нормальный вид Хомского. | Нормальный вид Хомского. | ||
+ | ''(9 сентября)'' | ||
=== Лекция 4: Представления обыкновенных грамматик === | === Лекция 4: Представления обыкновенных грамматик === | ||
Строка 44: | Строка 52: | ||
Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. | Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. | ||
Теорема Грейбах о «самом сложном языке». | Теорема Грейбах о «самом сложном языке». | ||
+ | ''(9 сентября)'' | ||
=== Лекция 5: Конъюнктивные грамматики === | === Лекция 5: Конъюнктивные грамматики === | ||
− | Определения конъюнктивных грамматик через логический вывод, перезапись термов, деревья разбора и языковые уравнения. Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. Приведение к нормальному виду Хомского. Понятие о булевых грамматиках. | + | Определения конъюнктивных грамматик |
+ | через логический вывод, перезапись термов, деревья разбора и языковые уравнения. | ||
+ | Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. | ||
+ | Приведение к нормальному виду Хомского. | ||
+ | Понятие о булевых грамматиках. | ||
+ | ''(11 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 5.pdf]] | [[Файл:Formal grammars 2014 lecture 5.pdf]] | ||
Строка 53: | Строка 67: | ||
=== Лекция 6: Однозначные грамматики === | === Лекция 6: Однозначные грамматики === | ||
− | Неоднозначность в естественных языках и языках программирования. Комбинаторные и аналитические методы доказательства существенной неоднозначности. | + | Неоднозначность в естественных языках и языках программирования. |
+ | Комбинаторные и аналитические методы доказательства существенной неоднозначности. | ||
+ | ''(11 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 6.pdf]] | [[Файл:Formal grammars 2014 lecture 6.pdf]] | ||
Строка 62: | Строка 78: | ||
Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность. | Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность. | ||
Лемма Терье. | Лемма Терье. | ||
+ | ''(12 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 7.pdf]] | [[Файл:Formal grammars 2014 lecture 7.pdf]] | ||
Строка 72: | Строка 89: | ||
Алгоритм проверки истинности формул логики FO(LFP) | Алгоритм проверки истинности формул логики FO(LFP) | ||
как прототип алгоритмов синтаксического анализа. | как прототип алгоритмов синтаксического анализа. | ||
+ | ''(12 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 8.pdf]] | [[Файл:Formal grammars 2014 lecture 8.pdf]] | ||
Строка 80: | Строка 98: | ||
Использование умножения матриц для ускорения алгоритма. | Использование умножения матриц для ускорения алгоритма. | ||
Умножение матриц по методу Штрассена и по методу Арлазарова и др. | Умножение матриц по методу Штрассена и по методу Арлазарова и др. | ||
+ | ''(22 сентября)'' | ||
[[Файл:Formal grammars 2014 lectures 9 10.pdf]] | [[Файл:Formal grammars 2014 lectures 9 10.pdf]] | ||
− | ( | + | (редакция от 30 сентября) |
=== Лекция 10: Табличные алгоритмы синтаксического анализа (окончание) === | === Лекция 10: Табличные алгоритмы синтаксического анализа (окончание) === | ||
Строка 88: | Строка 107: | ||
Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время. | Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время. | ||
Разбор для грамматик обёртывания пар. | Разбор для грамматик обёртывания пар. | ||
+ | ''(22 сентября)'' | ||
=== Лекция 11: Разбор сверху вниз === | === Лекция 11: Разбор сверху вниз === | ||
Строка 96: | Строка 116: | ||
Теорема Розенкранца--Стирнса | Теорема Розенкранца--Стирнса | ||
о регулярном объединении LL-языков. | о регулярном объединении LL-языков. | ||
+ | ''(22 сентября)'' | ||
[[Файл:Formal grammars 2014 lecture 11.pdf]] | [[Файл:Formal grammars 2014 lecture 11.pdf]] | ||
Строка 101: | Строка 122: | ||
=== Лекция 12: LR(k) анализ и детерминированные языки === | === Лекция 12: LR(k) анализ и детерминированные языки === | ||
− | Анализ через сдвиг и свёртку. Детерминированный конечный автомат, читающий стек. Класс LR(k) грамматик. Построение таблиц по методу SLR(k). Магазинные автоматы и их равносильность LR(k) грамматикам. | + | Анализ через сдвиг и свёртку. |
+ | Детерминированный конечный автомат, читающий стек. | ||
+ | Класс LR(k) грамматик. | ||
+ | Построение таблиц по методу SLR(k). | ||
+ | Магазинные автоматы и их равносильность LR(k) грамматикам. | ||
+ | ''(24 сентября)'' | ||
[[Файл:Formal grammars 2014 lectures 12 13.pdf]] | [[Файл:Formal grammars 2014 lectures 12 13.pdf]] | ||
− | (весьма неполная редакция от | + | (весьма неполная редакция от 25 сентября) |
=== Лекция 13: Автоматы, управляемые входом; обобщённый LR === | === Лекция 13: Автоматы, управляемые входом; обобщённый LR === | ||
Строка 110: | Строка 136: | ||
Автоматы, управляемые входом (input-driven automata; visibly pushdown automata). Равносильность их детерминированных и недетерминированных разновидностей. Грамматики, управляемые входом. | Автоматы, управляемые входом (input-driven automata; visibly pushdown automata). Равносильность их детерминированных и недетерминированных разновидностей. Грамматики, управляемые входом. | ||
Обобщённый LR: пример работы, оценки сложности. | Обобщённый LR: пример работы, оценки сложности. | ||
+ | ''(24 сентября)'' | ||
=== Лекция 14: Вычислительная сложность разбора === | === Лекция 14: Вычислительная сложность разбора === | ||
Строка 116: | Строка 143: | ||
разбор схемой высоты <math>(\log n)^2</math>. | разбор схемой высоты <math>(\log n)^2</math>. | ||
Линейная грамматика для NLOGSPACE-полного языка. | Линейная грамматика для NLOGSPACE-полного языка. | ||
− | Задача принадлежности данной | + | Задача принадлежности данной строки данной обыкновенной грамматике |
и её P-полнота. | и её P-полнота. | ||
Равносильность грамматик 1-го порядка классу 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 сентября) | ||
== Упражнения == | == Упражнения == | ||
Строка 133: | Строка 175: | ||
# Пусть <math>D=\{\varepsilon, ab, aabb, abab, aaabbb, \ldots\}</math> --- язык Дика над алфавитом <math>\{a, b\}</math>. Существует ли грамматика обёртывания пар для языка <math>L_4 = \{wc^{|w|} \mid w \in D\} = \{\varepsilon, abcc, aabbcccc, ababcccc, aaabbbcccccc, \ldots\}</math>? | # Пусть <math>D=\{\varepsilon, ab, aabb, abab, aaabbb, \ldots\}</math> --- язык Дика над алфавитом <math>\{a, b\}</math>. Существует ли грамматика обёртывания пар для языка <math>L_4 = \{wc^{|w|} \mid w \in D\} = \{\varepsilon, abcc, aabbcccc, ababcccc, aaabbbcccccc, \ldots\}</math>? | ||
# Построить грамматику 1-го порядка для языка <math>\{ww \mid w \in \{a, b\}^*\}</math>. | # Построить грамматику 1-го порядка для языка <math>\{ww \mid w \in \{a, b\}^*\}</math>. | ||
+ | |||
+ | [[Файл:Formal grammars 2014 homework 1 solutions.pdf]] | ||
+ | |||
+ | ''(проверенные работы переданы на кафедру)'' | ||
+ | |||
+ | === Задание 2: к 13 октября === | ||
+ | |||
+ | # Постоить обыкновенную грамматику ''в нормальном виде Хомского'' для языка Дика <math>D=\{\varepsilon, ab, aabb, abab, aaabbb, \ldots\}</math> над алфавитом <math>\{a, b\}</math>. Для этой грамматики и для входной строки <math>w=abaabba \notin D</math>, построить таблицу разбора <math>T_{i,j}</math>, как в алгоритме Кокка–Касами–Янгера. | ||
+ | # Рассмотреть работу алгоритма Валианта (синтаксический анализ через умножение матриц, лекции 9-10) для грамматики, построенной в прошлом упражнении. Среди всех действий, производимых алгоритмом, найти то произведение булевых матриц, после вычисления которого станет верным условие <math>S \in f(P_{0,6})</math>, где <math>S</math> — начальный символ грамматики. Описать, когда и как именно вычисляется это произведение — то есть, какая процедура, вызванная с какими значениями, и какой оператор в ней умножает какие две булевы матрицы какого размера, каков результат умножения, и какие элементы <math>P_{i,j}</math> будут этим затронуты? | ||
+ | # Замкнут ли класс LL языков относительно пересечения с регулярными языками? Если замкнут, привести построение (см. построение такого рода для всего класса обыкновенных грамматик в материалах к лекциям 2-4), а если незамкнут, привести пример LL грамматики и регулярного языка с доказательством несуществования LL грамматики для их пересечения (см. доказательства такого рода в материалах к лекции 11). | ||
+ | # Построить линейную грамматику для языка <math>f(L_0)</math>, где <math>L_0 = \{ w\$w^R \mid w \in \{a,b\}^* \}</math> и <math>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 \}</math> (это NLOGSPACE-полный язык, приведённый на лекции). | ||
+ | # Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку чётной длины»? Если разрешима, привести алгоритм, а если неразрешима, доказать это с помощью методов лекции 15 (использовав язык VALC в готовом виде, или же определив новый его вариант). | ||
+ | # Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку-палиндром <math>w</math>, т.е., строку, для которой <math>w=w^R</math>»? | ||
+ | # Для произвольной данной линейной грамматики G, пусть <math>L=\{vu \mid uv \in L(G)\}</math> — циклический сдвиг порождаемого ею языка. Построить алгоритм, определяющий принадлежность данной на входе строки языку <math>L</math>, и ''использующий как можно меньше памяти''. Объём памяти считать функцией <math>s(n)</math>, где <math>n</math> — длина входной строки, и этот объём должен быть по крайней мере меньше, чем линейным. Примечания: алгоритм строится по грамматике, и потому зависимостью требуемого объёма памяти от размера этой грамматики можно пренебречь; алгоритм должен быть детерминированным; если получится использовать алгоритмы, приведённые на лекциях, то их можно не повторять, но нужно указать, как именно и к чему именно они применяются. | ||
+ | |||
+ | ''(задания принимаются по эл. почте в формате pdf, печатном или отсканированном рукописном; отсканированные файлы должны быть пригодны для печати и умещаться в один мегабайт)'' | ||
+ | |||
+ | ''(11 декабря: все работы проверены, скоро будут результаты)'' | ||
+ | |||
+ | |||
+ | |||
+ | [[Category:Осень 2014]] |
Текущая версия на 12:54, 15 февраля 2015
Курс «Формальные грамматики»: сентябрь 2014 г., 15 лекций, лектор: Александр Охотин (университет Турку, Финляндия).
Содержание
- 1 Содержание лекций
- 1.1 Лекция 1: Введение, регулярные языки
- 1.2 Лекция 2: Обыкновенные грамматики
- 1.3 Лекция 3: Свойства обыкновенных грамматик
- 1.4 Лекция 4: Представления обыкновенных грамматик
- 1.5 Лекция 5: Конъюнктивные грамматики
- 1.6 Лекция 6: Однозначные грамматики
- 1.7 Лекция 7: Линейные грамматики
- 1.8 Лекция 8: Многокомпонентные грамматики, логика FO(LFP)
- 1.9 Лекция 9: Табличные алгоритмы синтаксического анализа
- 1.10 Лекция 10: Табличные алгоритмы синтаксического анализа (окончание)
- 1.11 Лекция 11: Разбор сверху вниз
- 1.12 Лекция 12: LR(k) анализ и детерминированные языки
- 1.13 Лекция 13: Автоматы, управляемые входом; обобщённый LR
- 1.14 Лекция 14: Вычислительная сложность разбора
- 1.15 Лекция 15: Разрешимость свойств грамматик
- 2 Упражнения
Содержание лекций
Приветствуются любые замечания по содержанию материалов к лекциям: если что-то неправильно или плохо понятно, то, пожалуйста, напишите, что именно.
Лекция 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: Вычислительная сложность разбора
Разбор обыкновенных грамматик с использованием памяти , разбор схемой высоты . Линейная грамматика для 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-го порядка для языка .
Файл:Formal grammars 2014 homework 1 solutions.pdf
(проверенные работы переданы на кафедру)
Задание 2: к 13 октября
- Постоить обыкновенную грамматику в нормальном виде Хомского для языка Дика над алфавитом . Для этой грамматики и для входной строки , построить таблицу разбора , как в алгоритме Кокка–Касами–Янгера.
- Рассмотреть работу алгоритма Валианта (синтаксический анализ через умножение матриц, лекции 9-10) для грамматики, построенной в прошлом упражнении. Среди всех действий, производимых алгоритмом, найти то произведение булевых матриц, после вычисления которого станет верным условие , где — начальный символ грамматики. Описать, когда и как именно вычисляется это произведение — то есть, какая процедура, вызванная с какими значениями, и какой оператор в ней умножает какие две булевы матрицы какого размера, каков результат умножения, и какие элементы будут этим затронуты?
- Замкнут ли класс LL языков относительно пересечения с регулярными языками? Если замкнут, привести построение (см. построение такого рода для всего класса обыкновенных грамматик в материалах к лекциям 2-4), а если незамкнут, привести пример LL грамматики и регулярного языка с доказательством несуществования LL грамматики для их пересечения (см. доказательства такого рода в материалах к лекции 11).
- Построить линейную грамматику для языка , где и (это NLOGSPACE-полный язык, приведённый на лекции).
- Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку чётной длины»? Если разрешима, привести алгоритм, а если неразрешима, доказать это с помощью методов лекции 15 (использовав язык VALC в готовом виде, или же определив новый его вариант).
- Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку-палиндром , т.е., строку, для которой »?
- Для произвольной данной линейной грамматики G, пусть — циклический сдвиг порождаемого ею языка. Построить алгоритм, определяющий принадлежность данной на входе строки языку , и использующий как можно меньше памяти. Объём памяти считать функцией , где — длина входной строки, и этот объём должен быть по крайней мере меньше, чем линейным. Примечания: алгоритм строится по грамматике, и потому зависимостью требуемого объёма памяти от размера этой грамматики можно пренебречь; алгоритм должен быть детерминированным; если получится использовать алгоритмы, приведённые на лекциях, то их можно не повторять, но нужно указать, как именно и к чему именно они применяются.
(задания принимаются по эл. почте в формате pdf, печатном или отсканированном рукописном; отсканированные файлы должны быть пригодны для печати и умещаться в один мегабайт)
(11 декабря: все работы проверены, скоро будут результаты)