a) Пусть задан автомат и известно, что число его состояний .
b) Зададим начальное приближение классов эквивалентности и сделаем это следующим образом: два состояния и относим в один класс эквивалентности , если и только если для всех входных знаков .
c) Пусть на шаге получено разбиение на классы эквивалентности , тогда на шаге два состояния и из одного класса эквивалентности относим в один класс если и только если иначе образуем новый класс куда заносим состояние и все другие состояния, для которых
d) Завершаем процедуру на шаге к , если этот шаг не изменяет разбиение на классы, иначе повторяем с).
Замечание: Алгоритм Мили конструктивен, так как число шагов не более чем n-1. По построению видно, что состояние из одного множества неотличимо.
Пример: Конечный автомат задан в виде автоматной таблицы.
A\Q q1 q2 q3 q4 q5 q6 q7 q8 q9
a1 q2/0 q1/1 q1/1 q8/0 q6/1 q8/0 q6/1 q4/1 q7/0
a2 q4/1 q1/0 q6/0 q1/1 q1/1 q9/1 q1/1 q4/0 q9/0
a3 q4/1 q5/0 q5/0 q1/1 q3/0 q6/1 q3/0 q7/0 q7/1
Задаем начальное приближение:
0. {q1, q4, q6, q9} {q2, q3, q8} {q5, q7}
шаг 1: два состояния относим в один класс (по числителю)
1. {q1, q4, q6} {q9} {q2, q3, q8} {q5, q7}
2. {q1, q4} {q6} {q9} {q2, q3, q8} {q5, q7}
3. {q1, q4} {q6} {q9} {q2, q3, q8 } {q5, q7 }
Так как разбиение на классы не изменилось, можно сделать вывод, что в минимальном автомате будет 6 состояний -–это С1, С2, С3, С4, С5, С6
A\Q0 C1 C2 C3 C4 C5 C6
a1 C4/0 C4/0 C6/0 C1/1 C1/1 C2/1
a2 C1/1 C3/1 C3/1 C1/0 C2/0 C1/1
a3 C1/1 C2/1 C6/1 C6/0 C6/0 C5/0
Т.3.3. Автомат Мура
Ранее данное определение конечному автомату описывает автомат, который называется автоматом Мили. В теории автоматов рассматривается другая форма представления конечного автомата, и та¬кой автомат называется автоматом Мура.
определение 12:Автоматом Мура называется такой конечный автомат, у которого функция входов не зависит от входного знака и зависит только от состояния.
Пусть . Eсли для любого состояния и для всех пар знаков то это автомат Мура.
Замечание: функция выходов является одноаргументной функцией .
-функция отметок, так как в автомате Мура выходной знак зависит только от состояния, в котором находится автомат, то на графе выходной знак пишется не на дуге, а внутри вершины состояний.
