ЛЕКЦИИ по курсу "Теория автоматов" (лектор к.ф-м.н., доцент В.А.Щербакова)

Последнее изменение: 23/06/2023 13:59:13

Лекция 1. Языки и конечные автоматы
Лекция 2. Приведенный ДКА
Лекция 3. НКА. Язык, допускаемый НКА
Лекция 4. НКА с epsilon-переходами
Лекция 5. Регулярные языки. Теорема Клини
Лекция 6. Поиск регулярного выражения по автомату. Теорема Ардена. Лемма о накачке
Лекция 7. Частные языка. Критерий регулярности в терминах левых частных, теорема Майхилла-Нероуда.
Лекция 8. Моноид переходов автомата. Распознавание языков моноидами, критерий регулярности. Синтаксический моноид языка.
Лекция 9. Типовые задачи по теории автоматов
Лекция 10. Автоматы-преобразователи (transducers). Машина Тьюринга. ДАМП.
Лекция 11. Синхронизируемые автоматы
Лекция 12. Алгоритм Кнута-Мориса-Прата. Автомат Ахо-Корасик.
Лекция 13. Замкнутость класса регулярных языков относительно операций: реверс, морфизмы, деление (частное), замыкания относительно префиксов, суффиксов, подслов

См. также

Нагребецкая Ю.В.