Дискретная математика: теория автоматов

Министерство цифрового развития, связи и массовых коммуникаций 

Российской Федерации

Федеральное государственное бюджетное образовательное учреждение 

высшего образования

«Сибирский государственный университет телекоммуникаций и 

информатики»

(СибГУТИ)

А. Ю. Овчаренко

Дискретная математика: теория автоматов

Учебно-методическое пособие

Новосибирск

2021

УДК 519.1

Утверждено редакционно-издательским советом СибГУТИ

Рецензент: д-р физ.-мат. наук, проф. Д.В. Лыткина

Овчаренко А. Ю. Дискретная математика: теория автоматов: 

Учебно-методическое 
пособие / А. 
Ю. 
Овчаренко;
Сибирский 

государственный университет телекоммуникаций и информатики; каф. высшей 
математики. – Новосибирск, 2021. – 24 с.

Пособие сдержит краткие теоретические сведения, примеры и задания по 

теории конечных
автоматов. Пособие предназначено для проведения 

практических занятий по теории автоматов при подготовке бакалавров.

Кафедра высшей математики СибГУТИ

Для подготовки студентов по направлениям
09.03.01 «Информатика и

вычислительная 
техника»,
квалификация 
(степень) 
бакалавра, 

02.03.02 «Фундаментальная информатика и информационные технологии»,
квалификация (степень) бакалавра.

© Овчаренко А.Ю., 2021

© Сибирский государственный университет
телекоммуникаций и информатики, 2021

Оглавление
Введение............................................................................................................... 4
1 Алфавиты и языки............................................................................................ 5
2 Детерминированные конечные автоматы...................................................... 9
3 Регулярные языки и регулярные выражения ..............................................14
4 Минимизация детерминированных конечных автоматов .........................16
Список литературы ...........................................................................................23