Формальные языки и трансляции 3. Полные ДКА

0:36 - Повторные определения 9:47 - Tеорема: минимальный по количеству состояний ПДКА - единственный с точностью до изоморфизма 28:10 - утверждение 1: q1 ~ q2 тогда и только когда w_q1 ~(L(M)) w_q2 32:27 - Следствие 36:36 - Вспомогательное определение 37:47 - Утверждение 2: при n не меньше |Q| - 2 все ~n одинаковы 38:53 - Утверждение 3 52:47 - Примеры неавтоматных языков 54:06 - Следствие из т. Майхилла-Нероуда 55:32 - Лемма о разрастании для автоматного языка 1:07:33 - Как проверить два RE на равенство Лекция от 20 сентября 2019 Лектор: Сорокин Алексей Андреевич Съемка - Юманов Михаил Монтаж - Бердовский Алексей