Материал: PZ_14_dlya_studentov

7) Ячейка (7,b)

Записываем в вторую строку 1, ниже – y.

1. В ячейке(1,b)=(3,x)

2. (3,b)=(1,x) Исходный автомат

Получили слово xxxxyxy.

Шаг 8. Проверим работу минимального автомата

По аналогии с предыдущим примером.

1. В ячейке(А,b)=(А,x)

2. (А,b)=(А,x)

3. (А,a)=(Б,x)

4. (Б,b)=(Г,x)

5. (Г,a)=(Б,y)

6. (Б,a)=(В,x)

7. (В,b)=(А,y)

xxxxyxy – полученное слово.

Слова, полученные при проверке работы двух автоматов, совпали. Значит, минимальный автомат найден верно!

Слова должны обязательно совпасть!

Шаг 9. Построим граф минимального автомата

Минимальный конечный автомат

Смотрим первый столбик А. Из него можно перейти в состояние Б и в состояние А. Рисуем ребро (А, Б) и петлю (А, А).

Смотрим второй столбик Б. Из него можно перейти в состояние В и в состояние Г. Рисуем ребро (Б, В) и ребро (Б, Г).

Смотрим третий столбик В. Из него можно перейти в состояние Б и в состояние А. Рисуем ребро (В, Б) и ребро (В, А).

Смотрим четвертый столбик Г. Из него можно перейти в состояние Б и в состояние В. Рисуем ребро (Г, Б) и ребро (Г, В).

Получен граф: