Поставим в соответствие каждой паре аi/xk состояние Ьik (i-номер состояния, k-номер входного сигнала), с учетом b0.
Составим таблицу переходов автомата Мура, руководствуясь следующими правилами:
1) Выпишем из таблицы 1.11 состояния автомата Мили и соответствующие каждому из них множества состояний автомата Мура (bik):
а0= {b0, b02, b11, b21}; a1= {b22}; а2= {b01, b12};
2) Если состояние автомата Мура bik входит в множество, соответствующее состоянию аp автомата Мили, то в строку таблицы переходов автомата Мура для состояния bik следует записать строку из таблицы переходов автомата Мили, соответствующую состоянию ар (из 1.10.).
3) Функцию выходов автомата Мура определим следующим образом: ?B (bik) =?A (аi, xk). Для начального состояния b0 значение выходного сигнала можно выбрать произвольно, но порождаемый начальным состоянием a0 (с учетом понятия эквивалентности состояний). Результирующая таблица переходов и выходов автомата Мура эквивалентного автомату Мили, заданному таблицей 1.10 представлена в таблице 1.12.
4) Найдем в таблице 1.12 эквивалентные состояния и удалим их (заменим на представителя класса эквивалентности).
Если выходной сигнал возле b0 доопределить y1, то окажется, что в данной таблице переходов находится 3 эквивалентных состояния (b0,b11,b02). Заменив класс эквивалентности одним представителем (b0), получим окончательную таблицу переходов (табл.1.13).
Таблица 1.12
x1
x2
Y
b0
b01
b02
y1
b21
b22
b11
b12
y2
Таблица 1.13.
У
Изложенные методы взаимной трансформации автоматов Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не изменяется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает.
Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.
y3
А
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
Выполним разбиение ?0:
?0={В1, В2, В3};
B1={a1, a2, a8}, В2={а6, а9, а10, а11, а12}, В3={а3, a4, a5, a7}.
Построим таблицу разбиения ?0:
B1
В2
В3
а4
х1
В3,
х2
B2
Выполним разбиение ?1:
?1={С1, С2, С3, С4};
C1={a1, a2, a8}, С2={а6, а9, а11}, С3={ а10, a12}, С4={а3, а4, a5, a7}.
Построим таблицу разбиения ?1:
С1
С2
С3
С4
C1
C4
Выполним разбиение ?2.
?1={D1, D2, D3, D4};
D1={a1, a2, a8}, D2={а6, а9, а11}, D3={ а10, a12}, D4={а3, а4, a5, a7}.
Разбиение ?2 повторяет разбиение ?1 - процедура разбиения завершена.
Выберем произвольно из каждого класса эквивалентности D1, D2, D3, D4 по одному представителю - в данном случае по минимальному номеру: A'={a1, а3, a6, а10}.
Удаляя из исходной таблицы переходов "лишние" состояния, определяем минимальный автомат Мура (табл.1.15.)
Таблица 1.15.
1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа" 1987.
2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.
Страницы: 1, 2, 3, 4