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

Материал из SEWiki
Перейти к: навигация, поиск
(Содержание лекций)
(Лекция 1: Введение, регулярные языки)
Строка 8: Строка 8:
 
Примеры. Замкнутость относительно основных действий.
 
Примеры. Замкнутость относительно основных действий.
 
Непредставимые множества.
 
Непредставимые множества.
 +
 +
[[Файл:Formal grammars 2014 lecture 1.pdf]]
  
 
=== Лекция 2: Обыкновенные грамматики ===
 
=== Лекция 2: Обыкновенные грамматики ===

Версия 21:07, 9 сентября 2014

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

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

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

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

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

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

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

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

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

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

Конъюнктивные грамматики

Однозначные грамматики

Линейные грамматики

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

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

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

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

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

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