Формальные грамматики 2014 — различия между версиями
Okhotin (обсуждение | вклад) |
Okhotin (обсуждение | вклад) (Выдано первое домашнее задание (к 22 сентября)) |
||
Строка 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>. |
Версия 01:03, 13 сентября 2014
Курс «Формальные грамматики»: сентябрь 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 Многокомпонентные грамматики, логика FO(LFP)
- 1.9 Табличные алгоритмы синтаксического анализа
- 1.10 Рекурсивный спуск
- 1.11 LR(k) анализ и детерминированные языки
- 1.12 Оценки сложности синтаксического анализа
- 1.13 Разрешимость свойств грамматик
- 2 Домашние задания
Содержание лекций
Лекция 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 сентября
- Построить обыкновенную грамматику для языка всех палиндромов: . Показать, как строка выводится с помощью перезаписи строк. Показать, что эта же строка принадлежит наименьшему решению системы языковых уравнений, построив несколько шагов последовательности .
- Доказать, что не существует обыкновенной грамматики для языка
- Построить конъюнктивную грамматику для языка .
- Построить однозначную обыкновенную грамматику для языка
- Является ли язык линейным конъюнктивным?
- Пусть --- язык Дика над алфавитом . Существует ли грамматика оборачивания пар для языка ?
- Построить грамматику 1-го порядка для языка .