5. Синтез дискретного автомата Мура.

5.1. Этап абстрактного синтеза.

Пусть требуется синтезировать асинхронный автомат Мура, начальное опи­сание которого представлено вход-выходной последовательностью:

x₀, x₁, x₂, x₃, x₄, x₁, x₂, x₄, x₂ – y₀, y₁, y₂, y₀, y₁, y₂, y₃, y₁, y₂

Определяем мощность входного и выходного множеств М_X = 5, M_Y = 4.

Строим первичную таблицу переходов-выходов автомата Мура (табл.1). Она имеет 5 строк по числу входных сигналов и 9 столбцов. При этом счита­ем, что каждому такту соответствует новое состояние автомата z_i, которому ставится в соответствие выходной сигнал y_k.

Считаем, что автомат Мура перед подачей входной последовательности находится в начальном состоянии z₀, в котором выходной сигнал не формируется. Реальное устройство может переходить в такое состояние при подключении источника питания. Отсутствие сигнала выходного алфавита на выходах устройства, когда автомат находится в начальном состоянии, обозначим символом y *.

При подаче входной последовательности автомат последовательно переходит в девять состояний, обозначенных z₁…z₉. Часть ячеек остается незапол­ненной. Для обеспечения устойчивой работы доопределяем автомат дополни­тельными переходами, в которых начальное и конечное состояния переходов совпадают (состояния в скобках). Первичный граф переходов-выходов (ГПВ) автомата Мура представлен на рис. 2.

Таблица 1 – Первичная таблица переходов-выходов автомата Мура

X	Состояния S и выходные сигналы Y
	y *	y0	y1	y2	y0	y1	y2	y3	y1	y2
	z0	z1	z2	z3	z4	z5	z6	z7	z8	z9
x0	z1	( z1 )								z1
x1		z2	( z2 )			z6	( z6 )
x2			z3	( z3 )			z7	( z7 )	z9	( z9 )
x3				z4	( z4 )
x4					z5	( z5 )		z8	( z8 )

5.2. Минимизация внутренних состояний.

Задача минимизации автомата сводится к возможно максимальному умень­шению числа внутренних состояний без изменения закона их функционирова­ния.

Решение этой задачи выполним методом Ауфенкампа и Хона, основанного на понятиях эквивалентных состояний.

Эквивалентными состояниями называются s_n и s_m такие состояния, кото­рым, во-первых, соответствуют одинаковые выходные сигналы y(t), а, во-вторых, переход из состояний s_n и s_m под воздействием любого символа при­водит к одному и тому же (или эквивалентному состоянию).

Это означает, что автомат, находящийся в этих состояниях под воздействием любой последовательности формирует одинаковые выходные последовательности.

Алгоритм оптимизации основан на разбиении множества состояний на непересекающиеся подмножества эквивалентных состояний и замена каждого подмножества эквивалентных состояний одним из его представителей.

Алгоритм минимизации:

1. методом последовательного разбиения выделяем все попарно эквива­лентные состояния;

2. объединяем эквивалентные состояния в одинаковые классы ₁,₂,… и выделяем в каждом классе по одному состоянию для выполнения последующих этапов, при разбиении на классы пустые клетки во внимание не принимаются;

3. строим вторичную таблицу переходов-выходов, в которой каждый класс состояний представляем только одним эквивалентным состоянием.

Первое разбиение состояний на классы выполняем по выходным сигналам (табл.2). Анализ таблицы 2 показывает, что в классе ₂ состояние z₂, а в классе ₃ состояние z₇ не являются эквивалентными остальным состояниям этих классов, т.к. при поступлении сигнала x₁ автомат переходит из состояния z₂ в класс состояний ₂, а при поступлении сигнала x₂ автомат переходит из состояния z₇ в класс состояний ₄, в отличие от других состояний класса, переводящих автомат под действием сигнала x₁ в состояния класса ₃, а под действием сигнала x₂ в состояния класса ₃. Поэтому состояния z₂ и z₇ выделяем в отдельные классы ₅ и ₆ соответственно (табл. 3).

Таблица 2 – Первое разбиение на классы состояний автомата Мура

X	Состояния S и выходные сигналы Y
	y *	y0	y0	y1	y1	y1	y2	y2	y2	y3
	z0	z1	z4	z2	z5	z8	z3	z6	z9	z7
x0	z1 (1)	z1 (1)							z1 (1)
x1		z2 (2)		z2 (2)	z6 (3)			z6 (3)
x2				z3 (3)		z9 (3)	z3 (3)	z7 (4)	z9 (3)	z7 (4)
x3			z4 (1)				z4 (1)
x4			z5 (2)		z5 (2)	z8 (2)				z8 (2)
Классы	0	1		2			3			4

Таблица 3 – Второе разбиение на классы состояний автомата Мура

X	Состояния S и выходные сигналы Y
	y *	y0	y0	y1	y1	y1	y2	y2	y2	y3
	z0	z1	z4	z2	z5	z8	z6	z3	z9	z7
x0	z1 (1)	z1 (1)							z1 (1)
x1		z2 (5)		z2 (5)	z6 (6)		z6 (6)
x2				z3 (3)		z9 (3)	z7 (4)	z3 (3)	z9 (3)	z7 (4)
x3			z4 (1)					z4 (1)
x4			z5 (2)		z5 (2)	z8 (2)				z8 (2)
Классы	0	1		5	2		6	3		4

На основании таблицы 3 строим вторичную таблицу переходов-выходов автомата Мура, эквивалентного исходному автомату, но содержащей только семь состояний вместо десяти (табл. 4).

Таблица 4 – Вторичная таблица переходов-выходов автомата Мура

X	Состояния S и выходные сигналы Y
	y *	y0	y1	y1	y2	y2	y3
	0	1	5	2	6	3	4
x0	1	1				1
x1		5	5	6	6
x2			3	3	4	3	4
x3		1				1
x4		2		2			2

Вторичный граф переходов-выходов автомата Мура представлен на рис. 3.