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

00:00:00 - Продолжение доказательства леммы о ПДКА 00:09:18 - Теорема о минимальном ПДКА 00:25:25 - Теорема о единственности ПДКА 00:48:12 - Алгоритм построения минимального ПДКА: слова малой длины 01:02:42 - Алгоритм построения минимального ПДКА: классы 01:03:32 - Теорема Майхилла-Нероуда 01:06:11 - Лемма о разрастании (лемма о накачке, pumping lemma) 01:13:42 - Как показать, что язык не является автоматным, используя отрицание леммы о разрастании? 01:15:38 - Пример: a^n b^n Дата лекции: 28.09.2021 Лектор: Ахтямов Павел Оператор: Мария Шкатова Монтаж: Алексей Горбулев