Формальные языки и трансляции 7. Нормальная форма Грейбах

ВНИМАНИЕ: с 12:30 ведется дискуссия по поводу замены определения переходов в МП-автомате, на 14:46 определение меняется.

Таймкоды:
0:30 - Повторное доказательство эквивалентности КС грамматик
4:42 - Доказательство шага индукции
16:07 - Доказательство теоремы
18:20 - Пример
21:52 - Определение НФ Грейбах
24:10 - Теорема: любую грамматику можно привести к НФ Грейбах
33:45 - Пояснение картинкой
35:33 - Лемма
58:30 - Правильное определение левого деления
Теорема - Любой магазин с МП эквивалентен автомату с переходами особого вида

Лекция от 18 октября 2019
Лектор: Сорокин Алексей Андреевич

Оператор: Юманов Михаил
Монтаж: Бердовский Алексей

[pupfer]

12:00 кажется переход снизу вверх нелегален, поскольку могут быть эпсилон переходы (например все В-шки кроме одной дают эпсилон, а одна из них конкатенацию всех слов). Впрочем эта лекция наполовину состоит из рукопашного надувательства.

[lectory_fpmi]

ВНИМАНИЕ: с 12:30 ведется дискуссия по поводу замены определения переходов в МП-автомате, на 14:46 определение меняется.

Таймкоды:
0:30 - Повторное доказательство эквивалентности КС грамматик
4:42 - Доказательство шага индукции
16:07 - Доказательство теоремы
18:20 - Пример
21:52 - Определение НФ Грейбах
24:10 - Теорема: любую грамматику можно привести к НФ Грейбах
33:45 - Пояснение картинкой
35:33 - Лемма
58:30 - Правильное определение левого деления
Теорема - Любой магазин с МП эквивалентен автомату с переходами особого вида