Формальные языки и трансляции 2. Детерминированные конечные автоматы

0:27 - Определение недетерминированного конечного автомата
1:43 - Теорема о существовании эквивалентного ДКА
6:45 - Доказательство теоремы
12:42 - Промежуточная лемма
20:08 - Доказательство основного утверждения
25:16 - Теорема о замкнутости автоматных языков относительно объединения, конкатенации, итерации
30:49 - Определение полного ДКА
31:34 - Утверждение об эквивалентности любого ДКА полному
33:46 - Теорема о замкнутости автоматных языков относительно дополнения и пересечения
45:14 - Определение регулярного выражения
47:41 - Приоритет операций
50:45 - Определение формального языка
51:33 - Теорема Клини
52:55 - Доказательство теоремы Клини
1:06:07 - Вопрос о нахождении минимального автомата
1:07:46 - Утверждение об эквивалентности слов, приходящих в одно и то же состояние
1:10:47 - Теорема Майхилла-Нероуда
1:15:26 - Промежуточная лемма

Лекция от 13 сентября 2019
Лектор: Сорокин Алексей Андреевич

Оператор: Рухадзе Альбина
Монтаж: Бердовский Алексей