7) Ячейка (7,b)
Записываем
в вторую строку 1, ниже – y.
|
b
|
b
|
a
|
b
|
a
|
a
|
b
|
1
|
3
|
1
|
2
|
6
|
9
|
7
|
1
|
|
х
|
x
|
х
|
х
|
y
|
х
|
y
|
В
ячейке(1,b)=(3,x)
(3,b)=(1,x)
Исходный автомат
|
b
|
b
|
a
|
b
|
a
|
a
|
b
|
1
|
3
|
1
|
2
|
6
|
9
|
7
|
1
|
|
х
|
x
|
х
|
х
|
y
|
х
|
y
|
Получили
слово xxxxyxy.
Шаг
8. Проверим
работу минимального автомата
По
аналогии с предыдущим примером.
В
ячейке(А,b)=(А,x)
(А,b)=(А,x)
(А,a)=(Б,x)
(Б,b)=(Г,x)
(Г,a)=(Б,y)
(Б,a)=(В,x)
(В,b)=(А,y)
|
b
|
b
|
a
|
b
|
a
|
a
|
b
|
А
|
А
|
А
|
Б
|
Г
|
Б
|
В
|
а
|
|
x
|
х
|
x
|
х
|
у
|
х
|
у
|
xxxxyxy
– полученное
слово.
Слова,
полученные при проверке работы двух
автоматов, совпали. Значит, минимальный
автомат найден верно!
Слова
должны обязательно совпасть!
Шаг
9. Построим
граф минимального автомата
Минимальный
конечный автомат
|
А
|
Б
|
В
|
Г
|
a
|
Б , x
|
В , x
|
Б , x
|
Б , y
|
b
|
А, x
|
Г ,
x
|
А , y
|
В , y
|
Смотрим
первый столбик А. Из него можно перейти
в состояние Б и в состояние А. Рисуем
ребро (А, Б) и петлю (А, А).
Смотрим
второй столбик Б. Из него можно перейти
в состояние В и в состояние Г. Рисуем
ребро (Б, В) и ребро (Б, Г).
Смотрим
третий столбик В. Из него можно перейти
в состояние Б и в состояние А. Рисуем
ребро (В, Б) и ребро (В, А).
Смотрим
четвертый столбик Г. Из него можно
перейти в состояние Б и в состояние В.
Рисуем ребро (Г, Б) и ребро (Г, В).
Получен
граф: