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

Материал из SEWiki
Перейти к: навигация, поиск
(Задание 1: к 22 сентября)
(Многокомпонентные грамматики, логика FO(LFP))
Строка 65: Строка 65:
 
[[Файл:Formal grammars 2014 lecture 7.pdf]]
 
[[Файл:Formal grammars 2014 lecture 7.pdf]]
  
=== Многокомпонентные грамматики, логика FO(LFP) ===
+
=== Лекция 8: Многокомпонентные грамматики, логика FO(LFP) ===
 +
 
 +
Грамматики обёртывания пар и грамматики надстройки деревьев (tree-adjoining grammars).
 +
Логика первого порядка над позициями в строке FO(LFP),
 +
представление грамматик в этой логике.
 +
Алгоритм проверки истинности формул логики FO(LFP)
 +
как прототип алгоритмов синтаксического анализа.
 +
 
 +
[[Файл:Formal grammars 2014 lecture 8.pdf]]
  
 
=== Табличные алгоритмы синтаксического анализа ===
 
=== Табличные алгоритмы синтаксического анализа ===

Версия 19:11, 16 сентября 2014

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Табличные алгоритмы синтаксического анализа

Рекурсивный спуск

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

Оценки сложности синтаксического анализа

Разрешимость свойств грамматик

Упражнения

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

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