Формальные языки и трансляции 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 Лектор: Сорокин Алексей Андреевич Оператор: Юманов Михаил Монтаж: Бердовский Алексей