Формальные языки и трансляции 5. Нормальная форма Хомского. Лемма о разрастании

0:30 - Нормальная форма Хомского 1:53 - Теорема о приведении грамматики к НФ Хомского 4:41 - 0й этап доказательства 5:08 - 1й этап доказательства 7:34 - 2й этап доказательства 9:36 - 3й этап доказательства 14:04 - 4й этап доказательства 16:03 - 5й этап доказательства 29:00 - Случай n=1 34:41 - Алгоритм Кока-Янгера-Касами 39:23 - Основная часть алгоритма 45:27 - Доказательство корректности алгоритма 52:30 - Сложность алгоритма 54:50 - Свойства КCГ 55:19 - Теорема о замкнутости KC-языков 1:01:26 - Лемма о разрастании для КС-языков 1:10:52 - Пример не КС-языка Лекция от 4 октября 2019 Лектор: Сорокин Алексей Андреевич Оператор: Рухадзе Альбина Монтаж: Бердовский Алексей