Концепции конечного автомата и регулярного языка. Операции над регулярными языками: Учебно-методическая разработка

Методическая разработка предназначена для самостоятельной работы студентов специальности ''Прикладная информатика'' над материалом темы, входящей в состав учебного курса ''Теория алгоритмов и математическая логика''. Вводятся понятие формального языка и действия над формальными языками, включая основные теоретико-множественные операции. Излагается концепция конечного автомата (в детерминированном и недетерминированном вариантах). Показывается, что операции, объединения, пересечения, дополнения, конкатенации и итерации не выводят из класса регулярных языков. Приводятся соответствующие алгоритмы синтеза конечных автоматов. Подготовлено на кафедре информатики и автоматизации научных исследований факультета ВМК ННГУ