Формальные языки и трансляции 2. Свойства конечных автоматов. Регулярные языки

00:00:00 начало
00:04:24 первый алгоритм: принадлежность слова автомату
00:14:50 строим автомат с однобуквенным переходом
00:19:20 о компиляторах
00:20:30 детерминированный конечный автомат
00:22:28 что станет с асимптотикой?
00:26:00 теорема (постороение ДКА)
00:31:17 обозначение (дельта для множества состояний)
00:32:43 замечание
00:34:00 определение дельта штрих
00:36:05 множество завершающих состояний
00:38:20 почему автомат детерминированный?
00:40:10 ещё один пример
00:40:44 лемма
00:42:49 замечание
00:45:05 доказательство леммы, база индукции
00:49:00 переход индукции
01:04:00 эквивалентные утверждения
01:09:45 следствие + определение ПДКА
01:11:15 теормема штрих (для любого ДКА можно построить ПДКА)
01:14:35 алгоритм детерминизации
01:18:10 свойства теоремы штрих
01:21:50 пример
Дата лекции: 12.09.2023
Лектор: Ахтямов Павел Ибрагимович
Оператор: Татаринов Гера
Монтажёр: Ванков Илья

Видео Формальные языки и трансляции 2. Свойства конечных автоматов. Регулярные языки канала Лекторий ФПМИ