Формальные языки и трансляции 4. МПДКА. Праволинейные грамматики

00:00:00 Начало 00:02:00 напоминание определения ПДКА (определение 1) 00:06:58 теорема существования единственного ПДКА с точностью до изоморфизма 00:06:57 определение изоморфизма (определение 2) 00:09:55 канонический автомат 00:14:04 разбор примера простого автомата 00:15:24 пишем изоморфизм для него 00:18:09 какие свойства надо показать, чтобы доказать, что это изоморфизм 00:24:27 обсуждение эквивалентности пси 00:27:15 согласованность стартовых состояний 00:28:17 согласованность завершающих состояний 00:31:11 согласованность переходов 00:39:00 почему четвёртый переход работает в обратную сторону 00:44:47 алгоритм минимизации ПДКА 00:48:17 лемма (ограничивает длину слова) 00:52:20 доказательство 00:55:27 исправление ошибки в лемме 01:08:00 теорема Майхилла-Нероуда 01:12:00 пример неавтоматного языка Дата лекции: Лектор: Ахтямов Павел Ибрагимович Оператор: Татаринов Гера Монтажёр: Ванков Илья