Формальные грамматики 2014 — различия между версиями
Okhotin (обсуждение | вклад) |
Okhotin (обсуждение | вклад) (→Содержание лекций) |
||
| Строка 1: | Строка 1: | ||
== Содержание лекций == | == Содержание лекций == | ||
| − | === Введение, регулярные языки === | + | === Лекция 1: Введение, регулярные языки === |
Математические модели синтаксиса. | Математические модели синтаксиса. | ||
| Строка 9: | Строка 9: | ||
Непредставимые множества. | Непредставимые множества. | ||
| − | === Обыкновенные грамматики === | + | === Лекция 2: Обыкновенные грамматики === |
Обыкновенные формальные грамматики | Обыкновенные формальные грамматики | ||
| Строка 22: | Строка 22: | ||
а также циклического сдвига. | а также циклического сдвига. | ||
| − | === Свойства обыкновенных грамматик === | + | === Лекция 3: Свойства обыкновенных грамматик === |
Языки, не представимые обыкновенными грамматиками. | Языки, не представимые обыкновенными грамматиками. | ||
| Строка 29: | Строка 29: | ||
Нормальный вид Хомского. | Нормальный вид Хомского. | ||
| − | === Представления обыкновенных грамматик === | + | === Лекция 4: Представления обыкновенных грамматик === |
Нормальный вид Грейбах. | Нормальный вид Грейбах. | ||
Версия 20:53, 9 сентября 2014
Содержание
- 1 Содержание лекций
- 1.1 Лекция 1: Введение, регулярные языки
- 1.2 Лекция 2: Обыкновенные грамматики
- 1.3 Лекция 3: Свойства обыкновенных грамматик
- 1.4 Лекция 4: Представления обыкновенных грамматик
- 1.5 Конъюнктивные грамматики
- 1.6 Однозначные грамматики
- 1.7 Линейные грамматики
- 1.8 Многокомпонентные грамматики, логика FO(LFP)
- 1.9 Табличные алгоритмы синтаксического анализа
- 1.10 Рекурсивный спуск
- 1.11 LR(k) анализ и детерминированные языки
- 1.12 Оценки сложности синтаксического анализа
- 1.13 Разрешимость свойств грамматик
Содержание лекций
Лекция 1: Введение, регулярные языки
Математические модели синтаксиса. Формальные языки. Конечные автоматы и регулярные выражения, их равносильность. Примеры. Замкнутость относительно основных действий. Непредставимые множества.
Лекция 2: Обыкновенные грамматики
Обыкновенные формальные грамматики (в терминологии Хомского, "бесконтекстные"). Определения через перезапись строк, через деревья разбора, через логический вывод и через языковые уравнения. Равносильность определений. Примеры грамматик. Замкнутость относительно объединения, конкатенации, звёздочки, а также циклического сдвига.
Лекция 3: Свойства обыкновенных грамматик
Языки, не представимые обыкновенными грамматиками. Лемма накачки, лемма Огдена. Грамматики над односимвольным алфавитом. Нормальный вид Хомского.
Лекция 4: Представления обыкновенных грамматик
Нормальный вид Грейбах. Нормальный вид Розенкранца. Теорема Хомского--Шюценберже о представлении обыкновенных языков через язык Дика. Теорема Грейбах о "самом сложном языке".
