filmov
tv
Формальные языки и трансляции 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 пример неавтоматного языка
Дата лекции: 26.09.2023
Лектор: Ахтямов Павел Ибрагимович
Оператор: Татаринов Гера
Монтажёр: Ванков Илья
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 пример неавтоматного языка
Дата лекции: 26.09.2023
Лектор: Ахтямов Павел Ибрагимович
Оператор: Татаринов Гера
Монтажёр: Ванков Илья