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

Материал из SEWiki
Перейти к: навигация, поиск
(Упражнения)
(Проставлены даты лекций)
Строка 11: Строка 11:
 
Примеры. Замкнутость относительно основных действий.
 
Примеры. Замкнутость относительно основных действий.
 
Нерегулярные языки.
 
Нерегулярные языки.
 +
''(8 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 1.pdf]]
 
[[Файл:Formal grammars 2014 lecture 1.pdf]]
Строка 26: Строка 27:
 
Замкнутость относительно объединения, конкатенации, звёздочки,
 
Замкнутость относительно объединения, конкатенации, звёздочки,
 
а также циклического сдвига.
 
а также циклического сдвига.
 +
''(8 сентября)''
  
 
[[Файл:Formal grammars 2014 lectures 2 3 4.pdf]]
 
[[Файл:Formal grammars 2014 lectures 2 3 4.pdf]]
Строка 37: Строка 39:
 
Грамматики над односимвольным алфавитом.
 
Грамматики над односимвольным алфавитом.
 
Нормальный вид Хомского.
 
Нормальный вид Хомского.
 +
''(9 сентября)''
  
 
=== Лекция 4: Представления обыкновенных грамматик ===
 
=== Лекция 4: Представления обыкновенных грамматик ===
Строка 44: Строка 47:
 
Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика.
 
Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика.
 
Теорема Грейбах о «самом сложном языке».
 
Теорема Грейбах о «самом сложном языке».
 +
''(9 сентября)''
  
 
=== Лекция 5: Конъюнктивные грамматики ===
 
=== Лекция 5: Конъюнктивные грамматики ===
  
Определения конъюнктивных грамматик через логический вывод, перезапись термов, деревья разбора и языковые уравнения. Примеры грамматик: wcw, объявление перед использованием, степени четвёрки. Приведение к нормальному виду Хомского. Понятие о булевых грамматиках.
+
Определения конъюнктивных грамматик
 +
через логический вывод, перезапись термов, деревья разбора и языковые уравнения.
 +
Примеры грамматик: wcw, объявление перед использованием, степени четвёрки.
 +
Приведение к нормальному виду Хомского.
 +
Понятие о булевых грамматиках.
 +
''(11 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 5.pdf]]
 
[[Файл:Formal grammars 2014 lecture 5.pdf]]
Строка 53: Строка 62:
 
=== Лекция 6: Однозначные грамматики ===
 
=== Лекция 6: Однозначные грамматики ===
  
Неоднозначность в естественных языках и языках программирования. Комбинаторные и аналитические методы доказательства существенной неоднозначности.
+
Неоднозначность в естественных языках и языках программирования.
 +
Комбинаторные и аналитические методы доказательства существенной неоднозначности.
 +
''(11 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 6.pdf]]
 
[[Файл:Formal grammars 2014 lecture 6.pdf]]
Строка 62: Строка 73:
 
Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность.
 
Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность.
 
Лемма Терье.
 
Лемма Терье.
 +
''(12 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 7.pdf]]
 
[[Файл:Formal grammars 2014 lecture 7.pdf]]
Строка 72: Строка 84:
 
Алгоритм проверки истинности формул логики FO(LFP)
 
Алгоритм проверки истинности формул логики FO(LFP)
 
как прототип алгоритмов синтаксического анализа.
 
как прототип алгоритмов синтаксического анализа.
 +
''(12 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 8.pdf]]
 
[[Файл:Formal grammars 2014 lecture 8.pdf]]
Строка 80: Строка 93:
 
Использование умножения матриц для ускорения алгоритма.
 
Использование умножения матриц для ускорения алгоритма.
 
Умножение матриц по методу Штрассена и по методу Арлазарова и др.
 
Умножение матриц по методу Штрассена и по методу Арлазарова и др.
 +
''(22 сентября)''
  
 
[[Файл:Formal grammars 2014 lectures 9 10.pdf]]
 
[[Файл:Formal grammars 2014 lectures 9 10.pdf]]
Строка 88: Строка 102:
 
Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время.
 
Разбор через умножение матриц (алгоритм Валианта). Разбор однозначных грамматик за квадратичное время.
 
Разбор для грамматик обёртывания пар.
 
Разбор для грамматик обёртывания пар.
 +
''(22 сентября)''
  
 
=== Лекция 11: Разбор сверху вниз ===
 
=== Лекция 11: Разбор сверху вниз ===
Строка 96: Строка 111:
 
Теорема Розенкранца--Стирнса
 
Теорема Розенкранца--Стирнса
 
о регулярном объединении LL-языков.
 
о регулярном объединении LL-языков.
 +
''(22 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 11.pdf]]
 
[[Файл:Formal grammars 2014 lecture 11.pdf]]
Строка 101: Строка 117:
 
=== Лекция 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]]
Строка 110: Строка 131:
 
Автоматы, управляемые входом (input-driven automata; visibly pushdown automata). Равносильность их детерминированных и недетерминированных разновидностей. Грамматики, управляемые входом.
 
Автоматы, управляемые входом (input-driven automata; visibly pushdown automata). Равносильность их детерминированных и недетерминированных разновидностей. Грамматики, управляемые входом.
 
Обобщённый LR: пример работы, оценки сложности.
 
Обобщённый LR: пример работы, оценки сложности.
 +
''(24 сентября)''
  
 
=== Лекция 14: Вычислительная сложность разбора ===
 
=== Лекция 14: Вычислительная сложность разбора ===
Строка 119: Строка 141:
 
и её P-полнота.
 
и её P-полнота.
 
Равносильность грамматик 1-го порядка классу P.
 
Равносильность грамматик 1-го порядка классу P.
 +
''(24 сентября)''
  
 
[[Файл:Formal grammars 2014 lecture 14.pdf]]
 
[[Файл:Formal grammars 2014 lecture 14.pdf]]
Строка 130: Строка 153:
 
Разрешимость задачи включения для автоматов, управляемых входом.
 
Разрешимость задачи включения для автоматов, управляемых входом.
 
Иерархия семейств грамматик.
 
Иерархия семейств грамматик.
 +
''(26 сентября)''
  
 
== Упражнения ==
 
== Упражнения ==

Версия 13:02, 29 сентября 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 (всё есть, но многoe нуждаeтся в редактировании; новая редакция будет позднее)

Лекция 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

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

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

Упражнения

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

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

Задание 2: (сочиняется)