Проектирование элементов ЭВУ, страница 4

Рис.2. Преобразование автомата Мили в автомат Мура

       Автомат Мили задан своим графом (рис.1) и совмещенной таблицей переходов и выходов (табл.17).

Табл.17. Совмещенная таблица переходов и выходов автомата Мили

Для перехода к автомату Мура найдем множества B_S , определяемые числом различных выходных сигналов на дугах, входящих в данное состояние (см. рис.1).

B₁ = {a₁W₃}={b₁}

B₂ = {a₂W₂}={b₂}

B₃ = {a₃W₂ , a₃W₄}={b₃ , b₄}

B₄ = {a₄W₂ , a₄W₄}={b₅ , b₆}

Составим таблицу переходов автомата Мура по таблице переходов автомата Мили и найденных состояний B_S (s = 1,2,3,4).

Табл.18. Таблица переходов автомата Мура

                                             a₁         a₂             a₃                     a₄

 

По полученной таблице переходов составляем граф автомата Мура (рис.3).

Рис.3. Граф автомата Мура

       Абстрактные автоматы Мили и Мура эквивалентны. Это можно проверить, подавая на входы автоматов некоторую последовательность Zбукв входного алфавита. При этом выходная последовательность Wобоих автоматов одинакова (начальные состояния автоматов – a₁ и b₁ соответственно).

2.2. Составление схемы алгоритма и программы, реализующей автомат Мура на языке ассемблера микропроцессора К580.

       Программа, моделирующая работу автомата Мура, должна реализовывать алгоритм его работы в соответствии с уравнениями:

,        

       Также она должна занимать, по возможности, наименьшее число ячеек памяти вычислителя. Роль элементов памяти автомата выполняют двоичные разряды ячеек памяти или регистров микропроцессорного устройства.

       Определим число двоичных разрядов, необходимое для представления кодов входных сигналов

;

и всех внутренних состояний (выходных сигналов)

; .

 

       Кодируем автомат.

Табл.19. Входные сигналы                             Табл.20. Внутренние состояния и выходные сигналы

Сост. входа	Биты кода
	x1	x2
Z1	0	0
Z2	0	1
Z3	1	0
Z4	1	1

Внут. сост.	Биты кода			Биты кода		Вых. сигнал
	Q1	Q2	Q3	y1	y2
b1	0	0	0	1	0	w3
b2	0	0	1	0	1	w2
b3	0	1	0	0	1	w2
b4	0	1	1	1	1	w4
b5	1	0	0	0	1	w2
b6	1	0	1	1	1	w4

       Переводим таблицу переходов (выходов) в двоичный алфавит.

Табл.21. Таблица переходов (выходов) в двоичном алфавите