Формальные грамматики 2014 — различия между версиями
Okhotin (обсуждение | вклад) (→Лекция 4: Представления обыкновенных грамматик) |
Okhotin (обсуждение | вклад) (→Линейные грамматики) |
||
| Строка 53: | Строка 53: | ||
[[Файл:Formal grammars 2014 lecture 6.pdf]] | [[Файл:Formal grammars 2014 lecture 6.pdf]] | ||
| − | === Линейные грамматики === | + | === Лекция 7: Линейные грамматики === |
| + | |||
| + | Обыкновенные линейные грамматики, лемма накачки для них. | ||
| + | Линейные конъюнктивные грамматики и клеточные автоматы, их равносильность. | ||
| + | Лемма Терье. | ||
| + | |||
| + | [[Файл:Formal grammars 2014 lecture 7.pdf]] | ||
=== Многокомпонентные грамматики, логика FO(LFP) === | === Многокомпонентные грамматики, логика FO(LFP) === | ||
Версия 23:34, 12 сентября 2014
Содержание
- 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 Разрешимость свойств грамматик
Содержание лекций
Лекция 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
