Рубцов А. Заметки и задачи о регулярных языках и конечных автоматах

М.: МФТИ, 2019. — 109 с.Эти заметки написаны по материалам моих семинаров по курсу «Теория и реализация языков программирования», которые я веду на факультете управления и прикладной математики МФТИ. В течение последних шести лет, я давал своим студентам еженедельные домашние задания, которые включали теоретический материал. В этом году я решил переработать еженедельные задания и скомпоновать их в единый текст, дополнив его материалом семинаров. Сил хватило только на половину курса — на часть, посвящённую регулярным языкам и конечным автоматам. В процессе написания текста я осознал, что рассказ без доказательств утверждений и особенно корректности алгоритмов не складывается, так что в итоге получилась небольшая книжка, которая покрывает первую половину курса.
Учебников, посвящённых формальным языкам и конечным автоматам (в которые традиционно входит тема этой книжки), написано немало (см. список литературы). Однако, благодаря плодотворной работе над курсом, которую ведёт коллектив преподавателей, в материалы курса вошли темы, полезные и естественные для изучения формальных языков и их приложений, но часто не отражаемые в учебной литературе (особенно русскоязычной). А именно: алгоритмы обработки текста на основе конечных автоматов, теорема МайхиллаҫНероуда (критерий регулярности языка), а также редко встречающееся описание регулярных языков уравнениями с регулярными коэффициентами.