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

Версия 01:03, 13 сентября 2014

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

Содержание

1 Содержание лекций
2 Домашние задания
- 2.1 Задание 1: к 22 сентября

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

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

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

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

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

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

Файл:Formal grammars 2014 lectures 2 3 4.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

Многокомпонентные грамматики, логика FO(LFP)

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

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

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

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

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

Домашние задания

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

Построить обыкновенную грамматику для языка всех палиндромов: $L_{1}=\{w\in \{a,b\}^{*}\mid w=w^{R}\}$ . Показать, как строка $ababa$ выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности $\varphi ^{k}(\bot )$ .
Доказать, что не существует обыкновенной грамматики для языка $L_{2}=\{a^{k_{1}}b\ldots a^{k_{n}}b\mid n\geqslant 1,0\leqslant k_{1}\leqslant \ldots \leqslant k_{n}\}$
Построить конъюнктивную грамматику для языка $L_{2}$ .
Построить однозначную обыкновенную грамматику для языка $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\}$
Является ли язык $L_{3}$ линейным конъюнктивным?
Пусть $D=\{\varepsilon ,ab,aabb,abab,aaabbb,\ldots \}$ --- язык Дика над алфавитом $\{a,b\}$ . Существует ли грамматика оборачивания пар для языка $L_{4}=\{wc^{|w|}\mid w\in D\}=\{\varepsilon ,abcc,aabbcccc,ababcccc,aaabbbcccccc,\ldots \}$ ?
Построить грамматику 1-го порядка для языка $\{ww\mid w\in \{a,b\}^{*}\}$ .

@@ Строка 79: / Строка 79: @@
 == Домашние задания ==
-=== Задание 1: к 22 сентября (ещё нет, но скоро будет) ===
+=== Задание 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>.