Алгоритм 1

1. Для каждого внутреннего состояния a_i, a_i € A, согласно (1) определяется множество U(a_i).

2. Обеспечивается выполнение условий (2). Последовательно просматриваются состояния множества A. Если для некоторого состояния a_i, a_i € A, нарушено условие (2), то выполняется расщепление состояния a_i.

Для этого вводится H = |U(a_i)| новых состояний a_i¹,...,a_i^H. Каждому состоянию a_i^h, h = ¯1,H, ставится в соответствие одно и только одно условие X(a_i^h) множества U(a_i). Для каждого состояния a_i^h, h = ¯1,H, определяются множества P(a_i^h) и C(a_i^h) следующим образом: P(a_i^h) := P(a_i), а C(a_i^h) образуется из всех переходов, которые осуществляются при выполнении условия X(a_i^h). Полагается: A := A \ {a_i} и A := A {a_i¹,...,a_i^H}.

Пункт 2 выполняется для всех состояний a_i множества А.

3. Вводятся дополнительные внутренние переменные для обеспечения ортогональности кодов внутренних состояний автомата класса E. Для этого строится троичная матрица W. Строки матрицы соответствуют внутренним состояниям множества A, а столбцы - переменным g₁,...,g_L. На пересечении строки i и столбца j матрицы W ставится единица, если входная переменная x_j входит в условие X(a_i) в прямом значении; ноль - в инверсном; и неопредел╦нное значение (дефис), если переменная x_j не входит в условие X(a_i).

Решается следующая задача: добавить в матрицу W минимальное число столбцов, соответствующих дополнительным переменным e₁,...,e_R, и закодировать строки матрицы W двоичными значениями переменных e₁,...,e_R таким образом, чтобы все строки матрицы W были взаимно ортогональны. Алгоритм решения последней задачи приводится в [1].

4. Определяются коды внутренних состояний автомата класса E. При этом код K(a_i) каждого состояния a_i, a_i € A, будет определяться содержимым соответствующей строки матрицы W.

5. Строится структурная таблица переходов конечного автомата, составляются логические уравнения функций переходов и выходов.

6. Конец.

Пример 1. В качестве примера рассмотрим синтез автомата Мили класса E, таблица переходов которого представлена в табл. 1. Отметим, что поскольку |A| = 5, то при синтезе автомата Мили класса A потребуется не менее тр╦х элементов памяти для хранения кодов внутренних состояний. Множества U(a_i), a_i € A, сформированные в результате выполнения пункта 1, приведены в табл. 2. Поскольку для состояний a₄ и a₅ нарушены условия (2), то согласно пункту 2 выполняется их расщепление, прич╦м состояние a₄ расщепляется на два состояния, состояние a₅ - на три. Построенная в пункте 3 матрица W показана в табл. 3 (первые четыре столбца). Для обеспечения ортогональности кодов внутренних состояний конечного автомата введены две дополнительные переменные e₁ и e₂, а также выполнено кодирование строк таблицы W (пятый и шестой столбец табл. 3). В результате определены следующие коды внутренних состояний:

K(a₁) = ¯g₄·¯e₁·¯e₂; K(a₂) = g₁·¯e₁·e₂; K(a₃) = ¯g₁·¯e₁·e₂; K(a₄¹) = g₁·¯g₂·e₁·¯e₂; K(a₄²) = g₃·e₁·e₂; K(a₅¹) = g₁·g₁·e₁·¯e₂; K(a₅²) = ¯g₃·e₁·e₂; K(a₅³) = g₄·¯e₁·¯e₂.

Таблица 1. Исходная таблица переходов автомата Мили

am	X(amas)	as	Y(amas)
a1	x1 ¯x1	a2 a3	y3,y4 y3,y4
a2	x1 x2 x1 ¯x2 ¯x1	a5 a4 a3	y4 y3 √
a3	x3 ¯x3	a4 a5	y3 y4
a4	x4 ¯x4	a5 a1	y2 √
a5	x4 ¯x4	a5 a1	y1 √

Таблица 2. Множества U(a_m)

am	U(am)
a1	¯x4
a2	x1
a3	¯x1
a4	x1 ¯x2; x3
a5	x1 x2; x3; x4

Таблица 3. Матрица W

	g1	g2	g3	g4	e1	e2
a1	-	-	-	0	0	0
a2	1	-	-	-	0	1
a3	0	-	-	-	0	1
a41	1	0	-	-	1	0
a4²	-	-	1	-	1	1
a51	1	1	-	-	1	0
a5²	-	-	0	-	1	1
a5³	-	-	-	1	0	0

Структурная таблица переходов представлена в табл. 4, на основании которой составляются следующие логические уравнения функций переходов и выходов:

d₁ = g₁·e₁·e₂·x₁·x₂ + g₁·e₁·e₂·x₁·x₂ + g₁·e₁·e₂; d₂ = ¯g₄·¯e₁·¯e₂ + g₁·¯e₁·e₂·¯x₁ + ¯g₁·¯e₁·e₂; y₁ = g₁·g₂·e₁·¯e₂·x₄ + ¯g₃·e₁·e₂·x₄ + g₄·¯e₁·¯e₂·x₄; y₂ = g₁·¯g₂·e₁·¯e₂¯x₄ + g₃·e₁·e₂·x₄; y₃ = ¯g₄·¯e₁·¯e₂ + g₁·­e₁·e₂·x₁·¯x₂ + ¯g₁·¯e₁·e₂·x₃; y₄ = ¯g₄·¯e₁·¯e₂ + g₁·¯e₁·e₂·x₁·x₂ + ¯g₁·¯e₁·e₂·¯x₃.

Таблица 4. Структурная таблица переходов автомата класса E

am	K(am)	X(am,as)	as	K(as)	Y(am,as)	D(am,as)
a1	¯g4╥¯e1╥¯e2	x1 ¯x1	a2 a3	g1╥¯e1╥e2 ¯g1╥¯e1╥e2	y3,y4 y3,y4	d2 d2
a2	g1╥¯e1╥e2	x1 x2 x1 ¯x2 ¯x1	a51 a41 a3	g1╥g2╥e1╥¯e2 g1╥¯g2╥e1╥¯e2 ¯g1╥¯e1╥e2	y4 y3 √	d1 d1 d2
a3	¯g1╥¯e1╥e2	x3 ¯x3	a4² a5²	g3╥e1╥e2¯g3╥e1╥e2	y3 y4	d1,d2 d1,d2
a41	g1╥¯g2╥e1╥¯e2	x4 ¯x4	a5³ a1	g4╥¯e1╥¯e2 ¯g4╥¯e1╥¯e2	y2 √	- -
a4²	g3╥e1╥e2	x4 ¯x4	a5³ a1	g4╥¯e1╥¯e2 ¯g4╥¯e1╥¯e2	y2 √	- -
a51	g1╥g2╥e1╥¯e2	x4 ¯x4	a5³ a1	g4╥¯e1╥¯e2 ¯g4╥¯e1╥¯e2	y1 √	- -
a5²	¯g3╥e1╥e2	x4 ¯x4	a5³ a1	g4╥¯e1╥¯e2 ¯g4╥¯e1╥¯e2	y1 √	- -
a5³	g4╥¯e1╥¯e2	x4 ¯x4	a5³ a1	g4╥¯e1╥¯e2 ¯g4╥¯e1╥¯e2	y1 √	- -

Окончательная реализация конечного автомата класса E показана на рис. 2.

Рисунок 2. Реализация на ПЛИС автомата класса E

Отметим, что в данном примере при синтезе автомата класса E, по сравнению с автоматом класса A, удалось на единицу сократить число макроячеек ПЛИС, необходимых для построения памяти конечного автомата.