Синтез конечных автоматов класса e

Пусть A - множество всех внутренних состояний конечного автомата. Определим множество A_E, A_E A, состояний автомата класса E, то есть множество состояний, коды которых определяются входными наборами. Пусть, как и прежде, конечный автомат задан таблицей переходов, столбцы которой имеют обозначения a_m, a_s, X(a_m,a_s) и Y(a_m,a_s). Обозначим через U(a_i) множество всех условий переходов в состояние a_i, a_i € A:

U(a_i) = {X(a_m,a_i) | a_m € B(a_i)}, (1)

где B(a_i) - множество состояний, переходы из которых оканчиваются в состоянии a_i. Обычно при реализации конечных автоматов на ПЛИС условие X(a_m,a_s) перехода автомата из состояния am в состояние as представляет собой некоторую элементарную конъюнкцию входных переменных. Однако в общем случае в качестве условия X(a_m,a_s) может выступать любая логическая функция, единичное значение которой вызывает переход автомата из состояния a_m в состояние a_s.

Состояние a_i, a_i € A, является состоянием автомата класса E, то есть a_i € A_E, если выполняются условия:

|U(a_i)| = 1, (2)

и

U(a_i) U(aj) = (3)

при i j для всех a_j € A.

Выполнение (2) обеспечивает осуществление всех переходов в состояние a_i по одному и тому же условию перехода (то есть состояние ai имеет только один код), а выполнение (3) обеспечивает то, что условия переходов в состояние a_i не вызывают переходов в другие состояния автомата (то есть состояния a_i и a_j имеют различные коды).

Условия (2) выполняются пут╦м расщепления состояний. Пусть, например, для некоторого состояния a_i, a_i € A, имеет место |U(a_i)| = H > 1. Можно расщепить состояние a_i на состояния a_i¹,...,a_i^H таким образом, чтобы переходы в каждое состояние a_i^h определялись только одним условием переходов, то есть выполнялось |U(a_i^h)| = 1, h = ¯1,H. Теперь вместо состояния a_i имеем H состояний, для которых выполняются условия (2). Выполнение условий (3) осуществляется пут╦м введения дополнительных переменных обратных связей и соответствующих им элементов памяти для различия кодов внутренних состояний автомата.

Условия (2) и (3) являются необходимыми, но не достаточными для построения конечного автомата класса E. Дело в том, что для детерминированности поведения конечного автомата все коды его внутренних состояний должны быть взаимно ортогональны. Однако однозначное соответствие различных входных наборов различным внутренним состояниям конечного автомата, то есть выполнение условия (3), ещ╦ не обеспечивает ортогональность кодов. Для сравнения, при синтезе автоматов классов А и В различные выходные наборы всегда ортогональны, так как это двоичные наборы. Входные же наборы представляют собой троичные векторы, прич╦мдоопределение безразличных значений входных переменных в общем случае не допустимо. Поэтому обязательным этапом синтеза конечных автоматов класса E является обеспечение ортогональности наборов входных переменных пут╦м их доопределения с помощью дополнительных внутренних переменных.

Суть метода синтеза конечного автомата класса E заключается в расщеплении всех состояний, для которых не выполняются условия (2), и введении внутренних переменных для обеспечения ортогональности кодов внутренних состояний. Пусть P(a_i) - множество переходов конечного автомата из состояния a_i; C(a_i) - множество переходов конечного автомата, которые оканчиваются в состоянии a_i, a_i € A; X(a_i) - некоторое условие перехода в состояние a_i, X(a_i) € U(a_i). Тогда алгоритм синтеза конечных автоматов класса E имеет следующий вид.