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