В данной курсовой работе будут рассмотрены основные понятия конечных автоматов, а также их эквивалентности и минимизации. Будет выполнено подробное решение нескольких типовых задач для подробного изучения алгоритмов минимизации конечных автоматов Мили и Мура.
Цель работы:
- Ознакомиться с теоретическими основами конечных автоматов-распознавателей;
- Представить несколько примеров построения конечных автоматов, распознающих некоторые языки.
Конечные автоматы [1] являются математической моделью устройств, перерабатывающих дискретную входную информацию в режиме «реального времени», т.е. в темпе ее поступления (рис.1).
Рисунок 1 — Автомат
На такие устройства в последовательные дискретные моменты времени 1,2, …, t, t+1,… поступают входные сигналы x(1),x(2), …, x(t),x(t+1),… и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), …, y(t), y(t+1),…. Конечные автоматы характеризуются двумя особенностями:
1. Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1), x(2), …, x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов λ(x(1), x(2), …, x(t)) = y(t), определяющая очередной выход по предшествующему входу.
— Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1), x(2), …, x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний S и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние q ϵ S, в котором находится автомат после получения входной последовательности x(1), x(2), …, x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.
1.1 Определение автоматов Мили и Мура
Определение 1. Конечным автоматом Мили (рис.2)[2] называется шестерка объектов: А = <S, X, Y, s 0 , δ, λ>, где
Теория автоматов (2)
... образом, множество инициальных автоматов описывается одним абстрактным автоматом. По характеру отсчета дискретного времени автоматы делятся на синхронные и асинхронные. В синхронных конечных автоматах моменты времени, в которые автомат ... 1. Общие сведения о теории автоматов Теория автоматов подразделяется на абстрактную и структурную теорию. Абстрактная теория автоматов рассматривает структуру без ...
- S — конечное непустое множество (состояний);
- X — конечное непустое множество входных сигналов (входной алфавит);
- Y — конечное непустое множество выходных сигналов (выходной алфавит);
- s 0 — начальное состояние;
- δ : S×X ® S — функция переходов;
- λ : S×X ® Y — функция выходов.
Для построения графа автомата Мили (рис.2) нам необходимо обозначить его состояния в виде вершин графа, а переходы и выходы — рёбрами.
Рисунок 2 — Графическое представление автомата Мили
Кроме графического способа (рис.2) отображения для автомата можно использовать и табличное (табл.1), задавая функции переходов и выходов в виде таблиц.
Таблица 1 — Табличное представление автомата Мили (таблицы переходов и выходов)
|
δ |
0 |
1 |
2 |
|
s0 |
s1 |
s2 |
s3 |
|
s1 |
s1 |
s0 |
s0 |
|
s2 |
s2 |
s1 |
s3 |
|
s3 |
s3 |
s3 |
s2 |
|
λ |
0 |
1 |
2 |
|
s0 |
y1 |
y2 |
y3 |
|
s1 |
y1 |
y0 |
y3 |
|
s2 |
y1 |
y2 |
y3 |
|
s3 |
y1 |
y2 |
y3 |
Определение 2. Конечным автоматом Мура (рис.3) называется шестерка объектов А = <S, X, Y, s0 , δ, λ>, где:
- S — множество состояний;
- X — входной алфавит;
- Y — выходной алфавит;
- s0 — начальное состояние;
- δ : S ´ X ® S — функция переходов;
- λ: S ® Y — функция выходов.
Для построения графа автомата Мура (рис.3) нам необходимо обозначить его состояния и выходы с помощью вершин графа, а переходы — с помощью рёбер.
Рисунок 3 — Графическое представление автомат Мура
Как и в случае с автоматом Мили для автомата Мура возможно и табличное представление (табл.2).
Таблица 2 — Табличное представление автомата Мура
|
s |
λ |
δ |
|
|
0 |
1 |
||
|
s0 |
y1 |
s1 |
s2 |
|
s1 |
y2 |
s1 |
s0 |
|
s2 |
y2 |
s2 |
s1 |
1.2 Эквивалентность конечных автоматов
Пусть S — алфавит (конечное множество символов) и S* — множество всех слов в алфавите S. Будем обозначать буквой e пустое слово, т.е. вовсе не содержащее букв (символов из S), а знаком × — операцию приписывания (конкатенации) слов.
Так, аав × ва = аавва. Знак × операции приписывания часто опускают.
Слова в алфавите S будем обозначать малыми греческими буквами a, b, g, …. Очевидно, e является единицей для операции приписывания:
ae = ea = a.
Очевидно также, что операция приписывания ассоциативна, т.е. (ab)g = a(bg).
Таким образом, множество S* всех слов в алфавите S относительно операции приписывания является полугруппой с единицей, т.е. моноидом;
S* называют свободным моноидом над алфавитом S.
Определение 3. Пусть А = (S, X, Y, s0 , d, l) — конечный автомат.
Расширенными функциями перехода и выхода автомата А называются функции
d *: S ´ X* ® S и l* : S ´ X* ® Y*,
определенные так:
d *(s, e) = s; d *(s, аa) = d *(d(s, а), a);
l*(s, e) = e; l*(s, аa)=l(s, а)×l*(d(s, а), a),
где а — любая буква входного алфавита X, а a — любое слово в алфавите X , т.е. a Î X*.
Расширенные функции переходов и выходов определены на множестве входных слов, в отличие от обычных функций переходов и выходов, которые определены на множестве входных сигналов — букв алфавита.
Пусть в некоторое состояние автомата не существует пути из начального состояния. Иными словами, в эти состояния автомат не может попасть.
Такие состояния автомата называются недостижимыми, остальные — достижимыми.
Очевидно, что недостижимые состояния и переходы из них можно отбросить: они не влияют на поведение конечного автомата. Дадим формальное определение.
Определение 4. Пусть А = (S, X, Y, s0 , d, l) — конечный автомат. Состояние sÎS называется достижимым тогда и только тогда, когда
($a Î X*) d*(s0 , a) = s
(т.е. под воздействием какого-либо входного слова автомат попадает в это состояние).
Таким образом, состояние s ÎS конечного автомата является недостижимым тогда и только тогда, когда
(«aÎ X*) d*(s0 , a) ¹ s
(т.е. под воздействием любого слова автомат не переходит в это состояние).
Множество D достижимых состояний КА автомата
А = (S, X, Y, s0 , d, l) строится с помощью алгоритма, основанного на индукции.
. Положим Q0 = {s0 }.
. На i-м шаге будем строить множество Qi состояний, достижимых из начального состояния автомата некоторого слова длины не более чем i.
Очевидно, что для любого i
Qi +1 = Qi È {d(s, x) | sÎQi , xÎX}.
. Ясно также, что не более чем за n = |S| шагов Qk+1 = Qk .
Положим D = Qk .
Определение 5. Конечные автоматы А = (SA , XA , YA , s0 A , dA , lA ) и В = (SB , XB , YB , s0 B , dB , lB ) называются эквивалентными, если выполнены два условия:
а) их входные алфавиты совпадают:
ХA = ХB = X;
б) реализуемые ими отображения выходов совпадают:
(«aÎ X*) l*A (s0A ,a) = l*B (s0B ,a) .
Определение 6. Прямым произведением конечных автоматов А =(SA , XA , YA , s0 A , dA , lA ) и В = (SB , XB , YB , s0 B , dB , lB ).
с одинаковый входным алфавитом X называется автомат
А´В = (SA ´SB , X, YA ´YB , (s0A , s0B ), dA ´ B , lA ´ B ),
где:
a) («sA Î SA ) («sB Î SB ) («xÎ X) dA ´ B ((sA , sB ),x) = (dA (sA , x), dB (sB , x));
б) («sA Î SA ) («sB Î SB ) («xÎ X) lA ´ B ((sA , sB ), x) = (lA (sA , x), lB (sB , x)).
Теорема Мура
Два конечных автомата с одинаковым входным алфавитом X являются эквивалентными тогда и только тогда, когда для любого достижимого состояния (sA , sB ) в их прямом произведении (рис.4) А ´ В справедливо [2]:
(«xÎX) lA (sA , x) = lB (sB , x).
Прямое произведение конечных автоматов А и В, изображенных на рис. 4, представлено на рис. 4А. На рис. 4В показан этот же автомат с выброшенными недостижимыми состояниями.
Рисунок 4 — Конечные автоматы
Рисунок 5 — Прямое произведение конечных автоматов
По графу переходов (рис.5) видно, что из всех достижимых состояний под воздействием входных сигналов автомат А ´ В выдает пары одинаковых выходных сигналов.
Следовательно, автоматы А и В эквивалентны.
1.3 Минимизация конечного автомата
Разные конечные автоматы могут функционировать одинаково, даже если у них разное число состояний. Важной задачей является нахождение минимального конечного автомата, который реализует заданное автоматное отображение [3].
Эквивалентными естественно назвать два состояния автомата, которые нельзя различить никакими входными словами.
Определение 1: Два состояния р и q конечного автомата
А = (S,X,Y,s0 ,d,l) называются эквивалентными (обозначается p~q), если («aÎ X*)l*(p,a) =l*(q, a).
Эквивалентные состояния можно объединить в один класс и построить новый автомат, состояниями которого являются классы эквивалентных состояний. Если мы можем определить на множестве состояний КА «максимально возможное» разбиение на классы эквивалентности, то, выбирая его классы эквивалентности как новые состояния, получим минимальный автомат, эквивалентный исходному.
Алгоритм минимизации КА
Алгоритм минимизации конечного автомата [3] [4] состоит в последовательном построении на множестве состояний автомата А разбиений p0 , p1 , …, p¥ , таких, что в один класс разбиения pk попадают k-эквивалентные состояния, т.е. те, которые неразличимы входными словами длиной £ k. Такие состояния будем считать находящимися в отношении эквивалентности ~k. Если p и q не являются k-эквивалентными, то р и q назовем k-различимыми. Из определения 1 вытекает, что
р ~kq Û («aÎ X*, |a| £ k) l*(p,a) =l*(q,a).
Очевидно, что в любом автомате все состояния 0-эквивалентны, поскольку при подаче пустого слова e на вход автомата выходом является также пустое слово e независимо от состояния, в котором автомат находится.
Следующее разбиение p1 также легко построить. Действительно, по определению в один блок p1 попадают все состояния, в которых автомат одинаково реагирует на входные сигналы: р ~1 q Û («xÎ X) l(p, x) =l(q, x).
Разбиения p0 , содержащее один единственный блок, в который входят все состояния автомата, и p1 , в каждом блоке которого собраны состояния, не различимые входными сигналами, являются исходными при построении цепочки разбиений p0 , p1 , …, p¥ .
Если мы сможем определить, как строить следующее разбиение из предыдущего, то начиная с p1 мы сможем последовательно построить и всю цепочку.
Теорема 2. Пусть р ~k q, k > 1. Для того чтобы p ~k+1 q, необходимо и достаточно, чтобы («xÎ X) d(p, x) ~k d(q, x).
Действительно, для того чтобы входное слово длины k+1, например, слово x0 x1 x2 …xk , не различала пару состояний р и q, нужно всего лишь, чтобы автомат из этих состояний переходил под воздействием х0 в такие состояния, которые не различимы словом x1 x2 …xk , т. е. чтобы d(p,x0 ) и d(q,x0 ) были бы k-неразличимы (см. рисунок).
Очевидно, что если р и q (k+1)-эквивалентны, то они k-эквивалентны. Иными словами, блоки разбиения pk +1 являются подблоками разбиения pk .
Поскольку число состояний конечно, может быть только конечное число последовательно уменьшающихся разбиений pk , начиная с «самого крупного» разбиения p0 , содержащего один единственный блок.
Более того, очевидно, что их не больше, чем число состояний конечного автомата.
Однако последовательное построение уменьшающихся разбиений, можно не продолжать дальше, как только два последовательных разбиения совпадают, поскольку справедлива теорема:
Теорема 3. Пусть pk+1 = pk . Тогда i > k Þ pi = pk . В частности, pk = p¥ .
Из этой теоремы следует, что как только мы получим совпадение pk+1 =pk , то алгоритм прекращает свою работу и разбиение p¥ = pk будет максимальным разбиением множества состояний конечного автомата на классы эквивалентных состояний, по которому и определяется минимальный конечный автомат, эквивалентный данному.
эквивалентность автомат распознаватель минимизация
2. Практическая часть
Пример 1
Минимизация конечного автомата Мили, заданного таблицей переходов (табл. 3) проводится последовательным построением разбиений π0, π1, …
Таблица 3 — таблица переходов для примера 1
|
S |
δ |
λ |
||
|
x1 |
x2 |
x1 |
x2 |
|
|
0 |
1 |
2 |
y1 |
y2 |
|
1 |
3 |
4 |
y3 |
y2 |
|
2 |
4 |
5 |
y3 |
y2 |
|
3 |
6 |
4 |
y1 |
y2 |
|
4 |
6 |
5 |
y1 |
y2 |
|
5 |
6 |
3 |
y1 |
y2 |
|
6 |
6 |
0 |
y1 |
y2 |
0) Начальное разбиение представляет собой один блок, включающий в себя все состояния, поскольку входные слова длиной 0 (пустое слово ε) не различают состояний: независимо от того, в каком состоянии автомат находился при подаче входа ε, выходом тоже будет ε.
Поэтому π0 = {A0 = {0,1,2,3,4,5,6}}.
1) Разбиение π1 в один блок объединяет те состояния, которые нельзя различить при подаче слов длиной 1.
Функция выходов λ при подаче слов x1 и x2 не может различить 0,3,4,5,6 поскольку для каждого из этих состояний при подаче на вход автомата x1 он выдаёт y1 , а при подаче на вход x2 он выдаёт y2 .
Состояния 1 и 2 попадают в другой блок, но между собой входным словом длины 1 их различить нельзя.
Поэтому π1 = {А1 = {0,3,4,5,6,}, B1 = {1,2}}
2) Следующее разбиение π2 объединяет в один блок те состояния, которые нельзя различить при подаче слов длиной 2.
Построим таблицу переходов (табл.2), но вместо значения состояния δ(S,x) будем писать блок разбиения π1 , в которое попадает δ(S,x).
Таким образом, например, δ(0,x1 ) = 1, а это состояние находится в блоке B1 ; δ(0,x2 ) = 2, а это состояние находится в блоке B1 .
Таблица 4 — таблица переходов для разбиения π2 .
|
S |
δ |
λ |
π1 |
|||
|
x1 |
x2 |
x1 |
x2 |
B1 |
B1 |
|
|
0 |
1 |
2 |
y1 |
y2 |
A1 |
A1 |
|
1 |
3 |
4 |
y3 |
y2 |
A1 |
A1 |
|
2 |
4 |
5 |
y3 |
y2 |
A1 |
A1 |
|
3 |
6 |
4 |
y1 |
y2 |
A1 |
A1 |
|
4 |
6 |
5 |
y1 |
y2 |
A1 |
A1 |
|
5 |
6 |
3 |
y1 |
y2 |
A1 |
A1 |
|
6 |
6 |
0 |
y1 |
y2 |
A1 |
A1 |
После такого построения видно, что состояния 0,3,4,5,6, нужно разбить на 2 блока {0} и {3,4,5,6}. Состояния 1 и 2 попадают в одни и те же блоки предыдущего разбиения π1 , поэтому они попадут в один и тот же блок разбиения π2 . Таким образом, π2 = {A2 = {0}, B2 = {3,4,5,6}, C2 = {1,2}}.
) Аналогично строится разбиение π3 .
Таблица 5 — Таблица переходов для разбиения π3
|
S |
δ |
λ |
π1 |
π2 |
||||
|
x1 |
x2 |
x1 |
x2 |
B1 |
B1 |
C2 |
C2 |
|
|
0 |
1 |
2 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
|
1 |
3 |
4 |
y3 |
y2 |
A1 |
A1 |
B2 |
B2 |
|
2 |
4 |
5 |
y3 |
y2 |
A1 |
A1 |
B2 |
B2 |
|
3 |
6 |
4 |
y1 |
y2 |
A1 |
A1 |
B2 |
|
|
4 |
6 |
5 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
|
5 |
6 |
3 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
|
6 |
6 |
0 |
y1 |
y2 |
A1 |
A1 |
B2 |
A2 |
На данном шаге блок {3,4,5,6} нужно разбить на два блока {3,4,5} и {6}.
Таким образом, π3 = {A3 = {0}, B3 = {3,4,5}, C3 = {6}, D3 = {1,2}}.
) Построим π4 .
Таблица 6 — Таблица переходов для разбиения π4
|
S |
δ |
λ |
π1 |
π2 |
π3 |
|||||
|
x1 |
x2 |
x1 |
x2 |
B1 |
B1 |
C2 |
C2 |
D3 |
D3 |
|
|
0 |
1 |
2 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
B3 |
B3 |
|
1 |
3 |
4 |
y3 |
y2 |
A1 |
A1 |
B2 |
B2 |
B3 |
B3 |
|
2 |
4 |
5 |
y3 |
y2 |
A1 |
A1 |
B2 |
B2 |
C3 |
B3 |
|
3 |
6 |
4 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
C3 |
B3 |
|
4 |
6 |
5 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
C3 |
B3 |
|
5 |
6 |
3 |
y1 |
y2 |
A1 |
A1 |
B2 |
B2 |
C3 |
B3 |
|
6 |
6 |
0 |
y1 |
y2 |
A1 |
A1 |
B2 |
A2 |
C3 |
A3 |
π4 = {A4 = {0}, B4 = {3,4,5}, C4 = {6}, D4 = {1,2}}.
Разбиение π4 совпадает с разбиением π3 . На основании теоремы 3 искомое разбиение π∞ совпадает с π3 .
Итак, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих собой блоки разбиения π3 , а его функции переходов и выходов представлены в таблице 7, а граф переходов на рис. 6.
Таблица 7 — Таблица переходов и выходов для минимизированного автомата из примера 1
|
S |
δ |
λ |
||
|
X1 |
X2 |
X1 |
X2 |
|
|
A |
D |
D |
y1 |
y2 |
|
B |
B |
C |
y1 |
y2 |
|
C |
C |
A |
y1 |
y2 |
|
D |
B |
B |
y3 |
y2 |
Рисунок 6 — Минимизированный автомат (пример 1)
Пример 2
Минимизация конечного автомата Мили, заданного таблицей переходов (табл. 8)
Таблица 8 — Таблица переходов для примера 2
|
S |
δ |
λ |
||||
|
α |
β |
γ |
α |
β |
γ |
|
|
1 |
2 |
2 |
5 |
1 |
1 |
1 |
|
2 |
1 |
4 |
4 |
0 |
1 |
1 |
|
3 |
2 |
2 |
5 |
1 |
1 |
1 |
|
4 |
3 |
2 |
2 |
0 |
1 |
1 |
|
5 |
6 |
4 |
3 |
1 |
1 |
1 |
|
6 |
8 |
9 |
6 |
0 |
1 |
1 |
|
7 |
6 |
2 |
8 |
1 |
1 |
1 |
|
8 |
4 |
4 |
7 |
1 |
1 |
1 |
|
9 |
7 |
9 |
7 |
0 |
1 |
1 |
) Начальное разбиение представляет собой один блок, включающий в себя все состояния, поскольку входные слова длиной 0 (пустое слово ε) не различают состояний: независимо от того, в каком состоянии автомат находился при подаче входа ε, выходом тоже будет ε.
Поэтому π0 = {A0 = {1,2,3,4,5,6,7,8,9}}.
) Разбиение π1 в один блок объединяет те состояния, которые нельзя различить при подаче слов длиной 1.
Функция выходов λ при подаче слов α, β и γ не может различить 1,3,5,7 и 8, поскольку для каждого из этих состояний при подаче на вход автомата α он выдаёт 1, при подаче на вход β — 1 и при подаче на вход γ он выдаёт 1.
Состояния 2,4,6 и 9 попадают в другой блок, но между собой входным словом длины 1 их различить нельзя.
Поэтому π1 = {A1 = {1,3,5,7,8}, B1 = {2,4,6,9}}.
) Следующее разбиение π2 объединяет в один блок те состояния, которые нельзя различить при подаче слов длиной 2.
Построим таблицу переходов (табл.9), но вместо значения состояния δ(S,x) будем писать блок разбиения π1 , в которое попадает δ(S,x).
Таблица 9 — Таблица переходов для разбиения π2
|
S |
δ |
λ |
π1 |
||||||
|
α |
Β |
γ |
α |
β |
γ |
α |
β |
γ |
|
|
1 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
|
2 |
1 |
4 |
4 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
|
3 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
|
4 |
3 |
2 |
2 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
|
5 |
6 |
4 |
3 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
|
6 |
8 |
9 |
6 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
|
7 |
6 |
2 |
8 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
|
8 |
4 |
4 |
7 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
|
9 |
7 |
9 |
7 |
0 |
1 |
1 |
A1 |
B1 |
A1 |
После такого построения видно, что состояния 2,4,6,9 нужно разбить на 2 блока {2,4,6} и {9}.
Таким образом, π2 = {A2 = {1,3,5,7,8}, B2 = {2,4,6}, C2 = {9}}.
3) Аналогично π3 (табл.10)
Таблица 10 — Таблица переходов для разбиения π3
|
S |
λ |
π1 |
π2 |
|||||||||
|
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
|
|
1 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
|
2 |
1 |
4 |
4 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
|
3 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
|
4 |
3 |
2 |
2 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
|
5 |
6 |
4 |
3 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
|
6 |
8 |
9 |
6 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
C2 |
B2 |
|
7 |
6 |
2 |
8 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
|
8 |
4 |
4 |
7 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
|
9 |
7 |
9 |
7 |
0 |
1 |
1 |
A1 |
B1 |
A1 |
A2 |
C2 |
A2 |
На данном шаге блок {2,4,6} нужно разбить на два блока {2,4} и {6}. Таким образом, π3 = {A3 = {1,3,5,7,8}, B3 = {2,4} C3 = {6}, D3 = {9}}.
) Построим π4 (табл.11)
Таблица 11 — Таблица переходов для разбиения π4
|
S |
δ |
λ |
π1 |
π2 |
π3 |
||||||||||
|
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
|
|
1 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
A3 |
|
2 |
1 |
4 |
4 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
A3 |
B3 |
B3 |
|
3 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
B3 |
|
4 |
3 |
2 |
2 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
A3 |
B3 |
B3 |
|
5 |
6 |
4 |
3 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
C3 |
B3 |
A3 |
|
6 |
8 |
9 |
6 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
C2 |
B2 |
A3 |
D3 |
C3 |
|
7 |
6 |
2 |
8 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
C3 |
B3 |
A3 |
|
8 |
4 |
4 |
7 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
A3 |
|
9 |
7 |
9 |
7 |
0 |
1 |
1 |
A1 |
B1 |
A1 |
A2 |
C2 |
A2 |
A3 |
D3 |
A3 |
На данном шаге блок {1,3,5,7,8} нужно разбить на два блока {1,3,8} и {5,7}.
π4 = {A4 = {1,3,8}, B4 = {5,7} C4 = {2,4}, D4 = {6}, E4 = {9}}.
) Построим π5 (табл.12)
Таблица 12 — Таблица переходов для разбиения π5
|
S |
δ |
λ |
π1 |
π2 |
π3 |
π4 |
||||||||||||
|
α |
β |
γ |
α |
β |
Γ |
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
α |
β |
γ |
|
|
1 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
A3 |
C4 |
C4 |
B4 |
|
2 |
1 |
4 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
A3 |
B3 |
B3 |
A4 |
C4 |
C4 |
|
|
3 |
2 |
2 |
5 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
B3 |
C4 |
C4 |
B4 |
|
4 |
3 |
2 |
2 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
B2 |
B2 |
A3 |
B3 |
B3 |
A4 |
C4 |
C4 |
|
5 |
6 |
4 |
3 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
C3 |
B3 |
A3 |
D4 |
C4 |
A4 |
|
6 |
8 |
9 |
6 |
0 |
1 |
1 |
A1 |
B1 |
B1 |
A2 |
C2 |
B2 |
A3 |
D3 |
C3 |
A4 |
E4 |
D4 |
|
7 |
6 |
2 |
8 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
C3 |
B3 |
A3 |
D4 |
C4 |
A4 |
|
8 |
4 |
4 |
7 |
1 |
1 |
1 |
B1 |
B1 |
A1 |
B2 |
B2 |
A2 |
B3 |
B3 |
A3 |
C4 |
C4 |
B4 |
|
9 |
7 |
9 |
7 |
0 |
1 |
1 |
A1 |
B1 |
A1 |
A2 |
C2 |
A2 |
A3 |
D3 |
A3 |
B4 |
E4 |
B4 |
π5 = {A5 = {1,3,8}, B5 = {5,7} C5 = {2,4}, D5 = {6}, E5 = {9}}.
Разбиение π5 совпадает с разбиением π4 . На основании теоремы 3 искомое разбиение π∞ совпадает с π4 .
Итак, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих собой блоки разбиения π4 , а его функции переходов и выходов представлены в таблице 13, а граф переходов на рисунке 7.
Таблица 13 — Таблица переходов и выходов для минимизированного автомата из примера 2.
|
S |
δ |
λ |
||||
|
α |
β |
γ |
α |
β |
γ |
|
|
A |
C |
C |
B |
1 |
1 |
1 |
|
B |
D |
C |
A |
1 |
1 |
1 |
|
C |
A |
C |
C |
0 |
1 |
1 |
|
D |
A |
E |
D |
0 |
1 |
1 |
|
E |
B |
E |
B |
0 |
1 |
1 |
Рисунок 7 — Минимизированный автомат (пример 2)
Пример 3
Минимизация конечного автомата Мура, заданного таблицей переходов (табл. 14)
Таблица 14 — Таблица переходов для примера 3
|
S |
λ |
δ |
|
|
x1 |
x2 |
||
|
1 |
y1 |
1 |
5 |
|
2 |
y2 |
2 |
5 |
|
3 |
y1 |
3 |
5 |
|
4 |
y1 |
4 |
2 |
|
5 |
y1 |
1 |
7 |
|
6 |
y1 |
2 |
2 |
|
7 |
y2 |
1 |
2 |
) Начальное разбиение представляет собой один блок, включающий в себя все состояния, поскольку входные слова длиной 0 (пустое слово ε) не различают состояний: независимо от того, в каком состоянии автомат находился при подаче входа ε, выходом тоже будет ε.
Поэтому π0 = {A0 = {1,2,3,4,5,6,7}}.
) Разбиение π1 в один блок объединяет те состояния, которые нельзя различить при подаче слов длиной 1.
Состояния 2 и 7 попадают в другой блок, но между собой входным словом длины 1 их различить нельзя.
Поэтому π1 = {А1 = {1,3,4,5,6}, B1 = {2,7}}
) Следующее разбиение π2 объединяет в один блок те состояния, которые нельзя различить при подаче слов длиной 2.
Построим таблицу переходов (табл.15), но вместо значения состояния δ(S,x) будем писать блок разбиения π1 , в которое попадает δ(S,x).
Таблица 15 — таблица переходов для разбиения π2 .
|
S |
λ |
δ |
π1 |
||
|
x1 |
x2 |
x1 |
x2 |
||
|
1 |
y1 |
1 |
5 |
A1 |
A1 |
|
2 |
y2 |
2 |
5 |
B1 |
A1 |
|
3 |
y1 |
3 |
5 |
A1 |
A1 |
|
4 |
y1 |
4 |
2 |
A1 |
B1 |
|
5 |
y1 |
1 |
7 |
A1 |
B1 |
|
6 |
y1 |
2 |
2 |
B1 |
B1 |
|
7 |
y2 |
1 |
2 |
A1 |
B1 |
После такого построения видно, что состояния 1,3,4,5,6 нужно разбить на 3 блока {1,3}, {4,5}, {6}, а состояния 2,7 — на два блока {2}, {7}.
Таким образом, π2 = {A2 = {1,3}, B2 = {4,5}, C2 = {6}, D2 ={2}, E2 ={7}}.
3) Переходы состояний 2,6,7 теперь можно не рассматривать, поскольку классы распались до первого элемента и меньше уже не станут. Обозначим это символами «-» в таблице.
Таблица 16 — Таблица переходов для разбиения π3
|
S |
λ |
δ |
π1 |
π2 |
|||
|
x1 |
x2 |
x1 |
x2 |
x1 |
x2 |
||
|
1 |
y1 |
1 |
5 |
A1 |
A1 |
A2 |
B2 |
|
2 |
y2 |
2 |
5 |
B1 |
A1 |
— |
— |
|
3 |
y1 |
3 |
5 |
A1 |
A1 |
A2 |
B2 |
|
4 |
y1 |
4 |
2 |
A1 |
B1 |
B2 |
D2 |
|
5 |
y1 |
1 |
7 |
A1 |
B1 |
A2 |
E2 |
|
6 |
y1 |
2 |
B1 |
B1 |
— |
— |
|
|
7 |
y2 |
1 |
2 |
A1 |
B1 |
— |
— |
π3 = {A3 = {1,3}, B3 = {4}, C3 = {5}, D3 = {6}, E3 ={2}, F3 ={7}}.
4) Построим π4 . Переходы состояний 4,5 также можно не рассматривать далее, поскольку классы не станут меньше в дальнейших итерациях.
Таблица 17 — Таблица переходов для разбиения π4
|
S |
λ |
δ |
π1 |
π2 |
π3 |
||||
|
x1 |
x2 |
x1 |
x2 |
x1 |
x2 |
x1 |
x2 |
||
|
1 |
y1 |
1 |
5 |
A1 |
A1 |
A2 |
B2 |
A3 |
C3 |
|
2 |
y2 |
2 |
5 |
B1 |
A1 |
— |
— |
— |
— |
|
3 |
y1 |
3 |
5 |
A1 |
A1 |
A2 |
B2 |
A3 |
C3 |
|
4 |
y1 |
4 |
2 |
A1 |
B1 |
B2 |
D2 |
— |
— |
|
5 |
y1 |
1 |
7 |
A1 |
B1 |
A2 |
E2 |
— |
— |
|
6 |
y1 |
2 |
2 |
B1 |
B1 |
— |
— |
— |
— |
|
7 |
y2 |
1 |
2 |
A1 |
B1 |
— |
— |
— |
— |
π4 = {A4 = {1,3}, B4 = {4}, C4 = {5}, D4 = {6}, E4 ={2}, F4 ={7}}.
Разбиение π4 совпадает с разбиением π3 . На основании теоремы 3 искомое разбиение π∞ совпадает с π3 .
Итак, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих собой блоки разбиения π3 , а его функции переходов и выходов представлены в таблице 18, а граф переходов на рисунке 8.
Таблица 18 — Таблица переходов и выходов для минимизированного автомата из примера 3.
|
S |
δ |
λ |
|
|
X1 |
X2 |
||
|
A |
A |
C |
y1 |
|
B |
B |
E |
y1 |
|
C |
A |
F |
y1 |
|
D |
E |
E |
y1 |
|
E |
E |
C |
y2 |
|
F |
A |
E |
y2 |
Рисунок 8 — Минимизированный автомат (пример 3)
Пример 4
Минимизация конечного автомата Мура, заданного таблицей переходов (табл. 19)
Таблица 19 — Таблица переходов для примера 4
|
S |
λ |
δ |
||
|
x1 |
x2 |
x3 |
||
|
a |
y1 |
d |
a |
e |
|
b |
y1 |
g |
b |
b |
|
c |
y2 |
g |
b |
b |
|
d |
y2 |
d |
b |
g |
|
e |
y1 |
d |
b |
g |
|
f |
y1 |
c |
a |
d |
|
g |
y2 |
g |
b |
d |
0) В данном примере начальное разбиение будет представлять собой два блока, включающих в себя все состояния.
Поэтому π0 = {A0 = {a,b,e,f}, B0 = {c,d,g}}.
1) Разбиение π1 в один блок объединяет те состояния, которые нельзя различить при подаче слов длиной 1.
Таблица 20 — Таблица переходов для разбиения π1
|
S |
λ |
δ |
π0 |
||||
|
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
||
|
a |
y1 |
d |
a |
e |
B0 |
A0 |
A0 |
|
b |
y1 |
g |
b |
b |
B0 |
A0 |
A0 |
|
c |
y2 |
g |
b |
b |
B0 |
A0 |
A0 |
|
d |
y2 |
d |
b |
g |
B0 |
A0 |
B0 |
|
e |
y1 |
d |
b |
g |
B0 |
A0 |
B0 |
|
f |
y1 |
c |
a |
d |
B0 |
A0 |
B0 |
|
g |
y2 |
g |
b |
d |
B0 |
A0 |
B0 |
π1 = {А1 = {a,b}, B1 = {e,f}, C1 = {c}, D1 = {d,g}}.
2) Следующее разбиение π2 объединяет в один блок те состояния, которые нельзя различить при подаче слов длиной 2.
Построим таблицу переходов (табл.21), но вместо значения состояния δ(S,x) будем писать блок разбиения π1 , в которое попадает δ(S,x).
Переходы состояния «с» теперь можно не рассматривать, поскольку классы распались до первого элемента и меньше уже не станут. Обозначим это символами «-» в таблице.
Таблица 21 — таблица переходов для разбиения π2 .
|
S |
λ |
δ |
π0 |
π1 |
||||||
|
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
||
|
a |
y1 |
d |
a |
e |
B0 |
A0 |
A0 |
D1 |
A1 |
B1 |
|
b |
y1 |
g |
b |
b |
B0 |
A0 |
A0 |
D1 |
A1 |
A1 |
|
c |
y2 |
g |
b |
b |
B0 |
A0 |
A0 |
— |
— |
— |
|
d |
y2 |
d |
b |
g |
B0 |
A0 |
B0 |
D1 |
D1 |
D1 |
|
e |
y1 |
d |
b |
g |
B0 |
A0 |
B0 |
D1 |
D1 |
D1 |
|
f |
y1 |
c |
a |
d |
B0 |
A0 |
B0 |
C1 |
D1 |
D1 |
|
g |
y2 |
g |
b |
d |
B0 |
A0 |
B0 |
C1 |
D1 |
D1 |
После построения видно, что состояния a,b и e,f нужно разбить на 2 блока {a}, {b} и {e}, {f}.
Таким образом, π2 = {A2 = {a}, B2 = {b}, C2 = {e}, D2 ={f}, E2 ={c}, F2 = {d,g}}.
) Построим разбиение π3 . Построим разбиение π3 . Переходы состояний «a», «b», «e», «f» можно не рассматривать далее, поскольку классы распались до первого элемента. Обозначим это символами «-» в таблице.
Таблица 22 — Таблица переходов для разбиения π3
|
S |
δ |
π0 |
π1 |
π2 |
|||||||||
|
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
||
|
a |
y1 |
d |
a |
e |
B0 |
A0 |
A0 |
D1 |
A1 |
B1 |
— |
— |
— |
|
b |
y1 |
g |
b |
b |
B0 |
A0 |
A0 |
D1 |
A1 |
A1 |
— |
— |
— |
|
c |
y2 |
g |
b |
b |
B0 |
A0 |
A0 |
— |
— |
— |
— |
— |
— |
|
d |
y2 |
d |
b |
g |
B0 |
A0 |
B0 |
D1 |
D1 |
D1 |
F2 |
B2 |
F2 |
|
e |
y1 |
d |
b |
g |
B0 |
A0 |
B0 |
D1 |
D1 |
D1 |
— |
— |
— |
|
f |
y1 |
c |
a |
d |
B0 |
A0 |
B0 |
C1 |
D1 |
D1 |
— |
— |
— |
|
g |
y2 |
g |
b |
d |
B0 |
A0 |
B0 |
C1 |
D1 |
D1 |
F2 |
B2 |
F2 |
π3 = {A3 = {a}, B3 = {b}, C3 = {e}, D3 ={f}, E3 ={c}, F3 = {d,g}}.
Разбиение π3 совпадает с разбиением π2 . На основании теоремы 3 искомое разбиение π∞ совпадает с π2 .
Итак, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих собой блоки разбиения π3 , а его функции переходов и выходов представлены в таблице 23, а граф переходов на рис. 9.
Таблица 23 — Таблица переходов и выходов для минимизированного автомата из примера 1
|
S |
δ |
λ |
||
|
X1 |
X2 |
X3 |
||
|
A |
F |
A |
C |
y1 |
|
B |
F |
B |
B |
y1 |
|
C |
F |
B |
F |
y1 |
|
D |
E |
A |
F |
y1 |
|
E |
F |
B |
B |
y2 |
|
F |
F |
B |
F |
y2 |
Рисунок 9 — Минимизированный автомат (пример 4)
Заключение
В процессе написания данной курсовой работы были изучены конечные автоматы Мили и Мура, эквивалентность и их минимизация. Подробно разобраны примеры решения типовых задач.
Список литературы
[Электронный ресурс]//URL: https://drprom.ru/kursovaya/teoriya-konechnyih-avtomatov/
1) НОУ Интуит, лекция «Конечные автоматы»
2) Карпов Ю.Г. Теория автоматов [Учебное издание для вузов]. Издательство: «Питер», 2003г., 206 стр.
) НОУ Институт, лекция «Минимизация и эквивалентность конечных автоматов»
) Минимизация конечных автоматов
