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

Дата лекции: 13.09.22
Лектор: Ахтямов Павел Ибрагимович

00:00:00 – начало. Конец доказательства теоремы прошлой лекции
00:13:40 – Как хранить автомат
00:16:00 – Удаление эпсилон-переходов на практике
00:20:55 – Принадлежность слова автоматному языку
00:28:40 – ДКА
00:33:40 – Теорема (построение ДКА)
00:42:30 – Лемма
01:00:05 – Окончание доказательства теоремы
01:04:40 – Сложность алгоритма построения ДКА
01:07:25 – ПДКА
01:09:45 – Свойства автоматных языков
01:15:50 – Проблема автоматов
01:18:10 – Теорема: любой язык, задающийся регулярным выражением, является автоматным. База индукции

Съёмка: Игорь Сенин