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

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

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

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

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

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

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

(СибГУТИ)

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

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

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

Новосибирск

2021

УДК 519.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

Наш курс называется «Теория автоматов и формальных языков». 

Данный курс является теоретическим. В этом курсе мы будем работать с 
абстрактными автоматами. Начнём мы с автоматов, распознающих слова 
(таких как детерминированные и недетерминированные конечные автоматы и 
автоматы с магазинной памятью), а затем поработаем также и с автоматами, 
которые способны что-то считать и вычислять (машины Тьюринга, РАМ-
машины). Также мы познакомимся с формальными языками и вычислимыми 
функциями, которые идут рука об руку с вышеперечисленными объектами.

Если работа с автоматами зачастую не требует особых теоретических

знаний и рассуждений, работа с языками потребует от нас способности 
мыслить абстрактно и разбираться в доказательствах, поэтому сделаем 
краткий экскурс в теорию формальных доказательств.

1 Алфавиты и языки

Алфавит – непустое конечное множество символов. Обозначение:  .
Примеры:




 
 0,1
 




 
,a b
 




 
, ,...,
a b
z
 


}
 
, ,..., ,.,,,:,
,
{
;,
...
a b
z
 



 ASCII


 Unicode

Словом (или цепочкой) над алфавитом  называется конечная

последовательность символов из  .

Примеры:

• 001

• abbab

• whale

• look! a whale!
Пустым словом называется слово, не содержащее ни одного

символа. Обозначение:   .

Множество всех слов над 
обозначается через 
*

.
Пример:





 0, 1
 
 
, 0, 1, 00, 01, 10, 11, 000, 001,  . . . 


 
.

Замечание 1.1. Символ 0 может обозначать как символ, так и слово, 

состоящее из одного символа. Но из контекста всегда ясно, о чём именно идёт 
речь.

Длина слова – количество символов, из которых оно состоит.

Обозначение:
w , где w

 – слово.

Примеры:


001
3



 
5
abbab 


 
!_
_
!
14
look
a
whale 


 
0
 

Обозначим через  n
 множество всех слов длины n над  . (Здесь

n
N

– натуральное число.)
Примеры:


0,1
 

•
 

0

 

•



1
0,1
   

•



2
,
,
,
aa bb ab ba
 

Замечание 1.2.

0
1
2
....

     

Введём также обозначение v
w

, означающее, что слово v

является началом слова w. Например,
aab
aabab

.

Пусть v , w


– слова. Конкатенацией слов v и w называется 

слово vw , полученное последовательной записью v и w слева направо. 
Через 

nv обозначается слово, полученное конкатенацией слова v с самим

собой n раз.

Замечание 1.3. Вообще говоря, vw и wv – разные слова. При этом

v
v
v



 .
Примеры: v
aba

, w
bb



vw
ababb

, wv
bbaba




2v
abaaba

, 

3
w
bbbbbb


Формальным
языком
(или
просто
языком)
над
алфавитом 

называется произвольное подмножество
 L


 (не обязательно конечное).

Примеры:



 
 0,  1
 
, 


 
 01, 001, 010, 111
L 




 
 
, 
a b
 
, 


|
 
 
  
 
n
n
L
a b
n
N


– множество, состоящее из всех слов 

вида 

n
n
a b , где n – натуральное число. Это, например, слова ab , 
,
aabb

aaabbb и т. д.




 
 0,  1
 
,
L – множество, состоящее из всех слов, в которых 

поровну 0 и 1. Это, например, слова   , 01, 10, 0101, 0011, 1001 и т. д.


 , 

5
 , 

* , ,  


Замечание 1.4.
 

 
. Первое множество не содержит вообще 

ничего, а второе содержит толькопустое слово.

Операции над языками. Пусть
*
,L K   – языки над  .


L
K

– пересечение L и K , т. е. множество всех слов, которые

лежат и в L , и в K.


L
K

– объединение L и K , т. е. множество всех слов, которые

лежат хотя бы в одном из языков L и K .



* \
L
L
 
– дополнение к L , т. е. множество всех слов над  ,

которые не лежат в L .


LK – конкатенация языков L и K , т. е. множество всех слов вида

vwvw, где v
L

, w
K

. Через

nL мы обозначаем конкатенацию

языка L с самим собой n раз.

Замечание 1.5.

1)
 

0
L



2)

nL – это не множество слов вида
n
w , это множество

всевозможных конкатенаций
1
2...
n
w w
w , где
iw
L
 .



*
0
1
2
 . . .
L
L
L
L




– звёздочка Клини, т. е. множество всевозможных

конкатенаций слов из L .

Примеры:
Дано 


, ,
a b c
 
,


, ,
,
L
a b ab abc

,


, ,
,
K
c bc abc


.

•


L
K
abc



•
,
{
,
,
,
}
,
,
L
K
a b c ab bc abc




•


,
,
,
, ,
,
,
,
,
,
,
,
,
LK
a ac abc aabc b bc bbc babc ab abbc ababc abcc abcbc abcabc


•
, , ,
,
,
,
,
,
,
, .
{
. }.
L
a b ab abc aa aab aabc abb ababc

 

Замечание 1.6.
 
 
L
L
L




, L
L
  
 .

Контрольные вопросы
1.1
Дайте определение термину алфавит. Приведите примеры.

1.2
Что называется словом над алфавитом. Приведите примеры.

1.3
Что означает пустое слово.

1.4
Чему равна длина слова:

a)
 work

b)
 10

c)
 
_
!
good
morning

d)  

1.5
Привести примеры множества всех слов длины:
a)
0


b)
1


c)
2


1.6
Что называется конкатенацией слов? Если v
dd

, w
aka

, то

слова будут равны

a) vw
b) wv

c)

2v

d)

3
w

e)
 v

f)
w


1.7
Дайте определение формальному языку.  Приведите пример.

1.8
Какие существуют операции над языками.

1.9
Дан алфавит


, ,
z x c
 
, и слова 


, ,
,
L
z x zx zxc

, 


, ,
,
K
c xc zxc


. 

Чему равно:

a)
L
K


b) L
K


c)
LK

d) L

2 Детерминированные конечные автоматы

Детерминированным конечным автоматом (сокращённо ДКА)

называется пятёрка 
0
, , ,
,
Q
q
F


, где:

• Q – множество состояний автомата (конечное);

•  – алфавит автомата (конечный);

•  – функция переходов;

•
0 
 
q
Q

– начальное состояние;

• F
Q

– множество заключительных состояний.

Конечные автоматы читают слова.  – алфавит, над которым 

задаются эти слова. В процессе чтения слова автомат переходит из одного 
состояния в другое. Q – множество состояний. Автомат находится в 
состоянии 
0q (старт), когда он начинает последовательно (слева направо) 

читать буквы слова. Из любого состояния по любой букве алфавита 
автомат может перейти в какое-то другое состояние в соответствии с 
функцией переходов  . Эта функция действует из множества Q в 
множество Q, т. е. сопоставляет паре 

1,
q а из состояния и буквы алфавита 

некоторое новое состояние 
2q . Это сопоставление означает, что, если,

находясь в состоянии
1q , автомат прочитает букву a , он перейдёт в 

состояние 
2q . Так он, читая некоторое слово, передвигается по состояниям. 

Если, дочитав слово до конца, автомат останавливается на одном из 
состояний из множества F (заключительное состояние), то мы говорим, 
что данное слово распознаётся (или допускается) данным конечным
автоматом.

Конечные автоматы удобно изображать в
графическом
виде

(рисунок 2.1). Вершинам соответствуют состояния автомата, а дуги
соответствуют функции переходов. Дуга из 
iq в 
jq помечена теми входными 

символами, которые переводят автомат из состояния 
iq в 
jq . Стартовое 

состояние принято обозначать треугольником или стрелкой, входящей в 
это состояние ниоткуда. Заключительное состояния помечены двойными
кружком.

Рисунок 2.1 – Пример изображения конечного автомата в виде графа

Замечание 2.1.

1)Слово «функция» в определении детерминированного конечного 

автомата имеет совершенно конкретный смысл. Оно означает, что 
для любых состояния
1q
Q

и символа 
a 
существует

единственное состояние
2q
Q

, такое, что 


1
2
, 
 
q
a
q


.
Это 

означает, что невозможны следующие ситуации:


Из какого-то состояния по какой-то букве нет перехода
дальше.


Из какого-то состояния по одной и той же букве есть
несколько переходов.

2)Множество заключительных состояний может быть пустым.

Пример 2.1. Построить детерминированный конечный автомат, 

допускающий (распознающий) все слова над алфавитом 

0,  1 , в которых нет 

двух последовательных единиц. Определить число слов длины k , входящих в 
L (рисунок 2.2).

, 0, 1, 00, 01, 10, 000, 001, 010, 100,
 101, 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010, . . . 
L

 








Рисунок 2.2 – Конечный автомат, распознающий все слова над алфавитом 



0,  1 , в которых нет двух последовательных единиц 


 





 
 
, , 
, 0, 1 , , , 
, 
 
A
A B C
A
A B















, 0  
 ; 
, 1  
 ; 
, 0  
 ; 
, 1  
 ; 
, 0  
 
, 1  
 
A
A
A
B
B
A
B
C
C
C
C













На рисунке 2.3 показана таблица переходов: табличное представление 

функции  . Здесь строки соответствуют состояниям, столбцы – входным 
символам. Начальное состояние помечено стрелкой, заключительные –
звёздочкой. На пересечении строки, соответствующей q , и столбца, 
соответствующего a, находится 


,  
q a

.

Если  – функция переходов, то 



– расширенная функция переходов.  

Расширенная функция переходов 



ставит в соответствие состоянию q и 

слову w состояние p , в которое автомат попадает из состояния q , обработав 

последовательность символов w.

Рисунок 2.3 – Пример представления функции  в таблице переходов

Определим 



по индукции. Базис. 

, 
 
 
q
q






. Шаг индукции. Пусть w

– слово вида xa . Тогда 



, 
 
  
 
, 
, 
q w
q x
a













 . Здесь w – слово, a – символ.

Соглашение:


. . . ,  ,  ,  ,  
w x y z – слова.


, , , . . .
a b c
– символы.

Расширенная функция переходов 



вычисляется по состоянию q и 

входному слову 
1
2 . . . 
n
a a
a , следуя пути, который начинается в q и проходит 

последовательно по дугам, помеченным символами 
1
2 . . . 
n
a a
a .

Пример 2.2. На рисунке 2.4 изображена таблица, которая задает таблицу

переходов: табличное представление функции  .

Рисунок 2.4 – Табличное представление функции 





















, 011  
 
, 01 , 1  
 
, 0 , 1 , 1  
 

 
, 1 , 1  
 
, 1  
  

B
B
B

A
B
C


 
  

 










Пусть


0
 
 
, , , 
, 
A
Q
q
F



– детерминированный конечный автомат.

Языком автомата
 
A называется множество
 




0
 
 
 
 
 
 
|  
,
 
L A
w
q
w
F



.

Язык – это множество цепочек, приводящих автомат из состояния 
0q в 

одно из заключительных состояний. Если язык L есть ( )
L A для некоторого 

детерминированного конечного автомата A , то L – регулярный язык.