Формальные грамматики 2014 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Однозначные грамматики)
м
 
(не показано 50 промежуточных версий 1 участника)
Строка 1: Строка 1:
 +
Курс «Формальные грамматики»: сентябрь 2014 г., 15 лекций,
 +
лектор: [http://users.utu.fi/aleokh/ Александр Охотин] (университет Турку, Финляндия).
 +
 
== Содержание лекций ==
 
== Содержание лекций ==
 +
 +
Приветствуются любые замечания
 +
по содержанию материалов к лекциям:
 +
если что-то неправильно или плохо понятно,
 +
то, пожалуйста, напишите, что именно.
  
 
=== Лекция 1: Введение, регулярные языки ===
 
=== Лекция 1: Введение, регулярные языки ===
Строка 5: Строка 13:
 
Математические модели синтаксиса.
 
Математические модели синтаксиса.
 
Формальные языки.
 
Формальные языки.
Конечные автоматы и регулярные выражения, их равносильность.
+
Детерминированные и недетерминированные конечные автоматы, регулярные выражения, их равносильность.
 
Примеры. Замкнутость относительно основных действий.
 
Примеры. Замкнутость относительно основных действий.
Непредставимые множества.
+
Нерегулярные языки.
 +
''(8 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 1.pdf]]
 
[[Файл:Formal grammars 2014 lecture 1.pdf]]
Строка 14: Строка 23:
  
 
Обыкновенные формальные грамматики
 
Обыкновенные формальные грамматики
(в терминологии Хомского, "бесконтекстные").
+
(в терминологии Хомского, «бесконтекстные»).
 
Определения через перезапись строк,
 
Определения через перезапись строк,
 
через деревья разбора,
 
через деревья разбора,
Строка 23: Строка 32:
 
Замкнутость относительно объединения, конкатенации, звёздочки,
 
Замкнутость относительно объединения, конкатенации, звёздочки,
 
а также циклического сдвига.
 
а также циклического сдвига.
 +
''(8 сентября)''
  
 
[[Файл:Formal grammars 2014 lectures 2 3 4.pdf]]
 
[[Файл:Formal grammars 2014 lectures 2 3 4.pdf]]
 +
(редакция от 16 сентября, добавлены все недостающие разделы)
  
 
=== Лекция 3: Свойства обыкновенных грамматик ===
 
=== Лекция 3: Свойства обыкновенных грамматик ===
Строка 33: Строка 44:
 
Грамматики над односимвольным алфавитом.
 
Грамматики над односимвольным алфавитом.
 
Нормальный вид Хомского.
 
Нормальный вид Хомского.
 +
''(9 сентября)''
  
 
=== Лекция 4: Представления обыкновенных грамматик ===
 
=== Лекция 4: Представления обыкновенных грамматик ===
Строка 39: Строка 51:
 
Нормальный вид Розенкранца.
 
Нормальный вид Розенкранца.
 
Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика.
 
Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика.
Теорема Грейбах о "самом сложном языке".
+
Теорема Грейбах о «самом сложном языке».
 +
''(9 сентября)''
  
 
=== Лекция 5: Конъюнктивные грамматики ===
 
=== Лекция 5: Конъюнктивные грамматики ===
  
Определения конъюнктивных грамматик через логический вывод, перезапись термов, деревья разбора и языковые уравнения. Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. Приведение к нормальному виду Хомского. Понятие о булевых грамматиках.
+
Определения конъюнктивных грамматик
 +
через логический вывод, перезапись термов, деревья разбора и языковые уравнения.
 +
Примеры грамматик: wcw, объявление перед использованием, степени четвёрки.
 +
Приведение к нормальному виду Хомского.
 +
Понятие о булевых грамматиках.
 +
''(11 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 5.pdf]]
 
[[Файл:Formal grammars 2014 lecture 5.pdf]]
Строка 49: Строка 67:
 
=== Лекция 6: Однозначные грамматики ===
 
=== Лекция 6: Однозначные грамматики ===
  
Неоднозначность в естественных языках и языках программирования. Комбинаторные и аналитические методы доказательства существенной неоднозначности.
+
Неоднозначность в естественных языках и языках программирования.
 +
Комбинаторные и аналитические методы доказательства существенной неоднозначности.
 +
''(11 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 6.pdf]]
 
[[Файл: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: Вычислительная сложность разбора ===
 +
 
 +
Разбор обыкновенных грамматик с использованием памяти <math>(\log n)^2</math>,
 +
разбор схемой высоты <math>(\log n)^2</math>.
 +
Линейная грамматика для 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 сентября ===
 +
 
 +
# Построить обыкновенную грамматику для языка всех палиндромов: <math>L_1 = \{ w \in \{a, b\}^* \mid w=w^R \}</math>. Показать, как строка <math>ababa</math> выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности <math>\varphi^k(\bot)</math>.
 +
# Доказать, что не существует обыкновенной грамматики для языка <math>L_2=\{ a^{k_1} b \ldots a^{k_n} b \mid n \geqslant 1, 0 \leqslant k_1 \leqslant \ldots \leqslant k_n \}</math>
 +
# Построить конъюнктивную грамматику для языка <math>L_2</math>.
 +
# Построить однозначную обыкновенную грамматику для языка <math>L_3=\{c^m a^{\ell_0}b \ldots a^{\ell_{m-1}}b a^{\ell_m}b \ldots a^{\ell_z}b d^n \mid m,n, \ell_i \geqslant 0, z \geqslant 1, \ell_m=n\}</math>
 +
# Является ли язык <math>L_3</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>.
 +
 
 +
[[Файл:Formal grammars 2014 homework 1 solutions.pdf]]
 +
 
 +
''(проверенные работы переданы на кафедру)''
 +
 
 +
=== Задание 2: к 13 октября ===
  
=== Многокомпонентные грамматики, логика FO(LFP) ===
+
# Постоить обыкновенную грамматику ''в нормальном виде Хомского'' для языка Дика <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 декабря: все работы проверены, скоро будут результаты)''
  
=== LR(k) анализ и детерминированные языки ===
 
  
=== Оценки сложности синтаксического анализа ===
 
  
=== Разрешимость свойств грамматик ===
+
[[Category:Осень 2014]]

Текущая версия на 12:54, 15 февраля 2015

Курс «Формальные грамматики»: сентябрь 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: Вычислительная сложность разбора

Разбор обыкновенных грамматик с использованием памяти , разбор схемой высоты . Линейная грамматика для 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. Построить обыкновенную грамматику для языка всех палиндромов: . Показать, как строка выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности .
  2. Доказать, что не существует обыкновенной грамматики для языка
  3. Построить конъюнктивную грамматику для языка .
  4. Построить однозначную обыкновенную грамматику для языка
  5. Является ли язык линейным конъюнктивным?
  6. Пусть --- язык Дика над алфавитом . Существует ли грамматика обёртывания пар для языка ?
  7. Построить грамматику 1-го порядка для языка .

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

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

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

  1. Постоить обыкновенную грамматику в нормальном виде Хомского для языка Дика над алфавитом . Для этой грамматики и для входной строки , построить таблицу разбора , как в алгоритме Кокка–Касами–Янгера.
  2. Рассмотреть работу алгоритма Валианта (синтаксический анализ через умножение матриц, лекции 9-10) для грамматики, построенной в прошлом упражнении. Среди всех действий, производимых алгоритмом, найти то произведение булевых матриц, после вычисления которого станет верным условие , где — начальный символ грамматики. Описать, когда и как именно вычисляется это произведение — то есть, какая процедура, вызванная с какими значениями, и какой оператор в ней умножает какие две булевы матрицы какого размера, каков результат умножения, и какие элементы будут этим затронуты?
  3. Замкнут ли класс LL языков относительно пересечения с регулярными языками? Если замкнут, привести построение (см. построение такого рода для всего класса обыкновенных грамматик в материалах к лекциям 2-4), а если незамкнут, привести пример LL грамматики и регулярного языка с доказательством несуществования LL грамматики для их пересечения (см. доказательства такого рода в материалах к лекции 11).
  4. Построить линейную грамматику для языка , где и (это NLOGSPACE-полный язык, приведённый на лекции).
  5. Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку чётной длины»? Если разрешима, привести алгоритм, а если неразрешима, доказать это с помощью методов лекции 15 (использовав язык VALC в готовом виде, или же определив новый его вариант).
  6. Разрешима ли такая задача: «по данной обыкновенной грамматике, определить, порождает ли она хотя бы одну строку-палиндром , т.е., строку, для которой »?
  7. Для произвольной данной линейной грамматики G, пусть — циклический сдвиг порождаемого ею языка. Построить алгоритм, определяющий принадлежность данной на входе строки языку , и использующий как можно меньше памяти. Объём памяти считать функцией , где — длина входной строки, и этот объём должен быть по крайней мере меньше, чем линейным. Примечания: алгоритм строится по грамматике, и потому зависимостью требуемого объёма памяти от размера этой грамматики можно пренебречь; алгоритм должен быть детерминированным; если получится использовать алгоритмы, приведённые на лекциях, то их можно не повторять, но нужно указать, как именно и к чему именно они применяются.

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

(11 декабря: все работы проверены, скоро будут результаты)