Эквивалентность автоматов Мили и Мура.
Как отмечалось выше, любой конечный автомат может быть описан либо как автомат Мили либо как автомат Мура, т.е. эти две модели автоматов эквивалентны между собой.
Напомним, что модели автомата Мили описывается двумя характеристическими функциями функцией переходов и функцией выходов:
Y(t)=Fy[X(t),Y(t)];
S(t+1)=Fs[X(t),Y(t)].
В свою очередь, модель автомата Мура описывается функцией выходов и функцией переходов вида
Y’(t)=F’y(X(t),S’(t));
Рассмотрим переход от произвольного автомата Мили к эквивалентному ему Мура.
Пусть конечный автомат Мили задан своими функциями выходов и переходов. Найдем функцию выходов и переходов эквивалентного ему автомата Мура. Для этого поставим в соответствие каждой паре (X(t),S(t)) автомата Мили состояние S’ij автомата Мура. Кроме того, в множество состояний автомата Мура включим начальное состояние автомата Мили So, обозначив его через S’o.
Переходы из состояний автомата Мура определяются следующим образом. Пусть автомат Мили под воздействием входного сигнала xi переходит из состояния Sj(Sj≠So) в состояние Sq, т.е. Fs[X(t),Sj(t)]=Sq. В этом случае эквивалентный этому автомат Мура под воздействием сигнала Xr должен переходит из состояния S’ij в состояние S’qr, т.е. F’s[Pr(t);Sij(t)]=S’qr.
Переходы из начального состояния S’o для автомата Мура определяются как F’s[Xr(t);S’o(t)]=S’o2.
Так как мы приняли, что F’ij=[X(t);Sj(t)], то алгоритм получения функции переходов автомата Мура, эквивалентного данному автомату Мили, описывается функциями:
F’s[X1r(t), (Xi(t)Sj(t))]=F’s[Xr(t)Fs(Xi(t)Sj(t))] при Si≠So и
F’s[Xr(t),So(t)]=Fs[Xr(t)So(t)]=S’o2
Если автомат Мили имеет q состояний и n входных сигналов, то число внутринних состояний автомата Мура равно qn+1.
Определим, в какое состояние перейдет автомат Мура из состояния So под воздействием X1.
Автомат Мили из состояния So под воздействием X1 переходит в состояние S1. В свою очередь автомат Мура из состояния S’o под воздействием X1 должно перейти в состояние S’o1.
Пример. Автомат Мили, определенный на множествах X={x1,x2}, Y={y1,y2,y3} и S={s0,s1,s2,s3} задан таблицами переходов (табл. 3.6) и выходов (табл.3.7).
| xj | si | xj | si | |||||||
| s0 | s1 | s2 | s3 | s0 | s1 | s2 | s3 | |||
| x1 | s1 | s2 | s3 | s3 | x1 | y2 | y2 | y1 | y2 | |
| x2 | s0 | s2 | s0 | s1 | x2 | y2 | y2 | y2 | y2 |
Табл. 3.6
Табл. 3.7
В таблице 3.8 приведено кодирование заданного автомата Мили состояниями эквивалентного ему автомата Мура.
| xj | si | |||
| s0 s’0 | s1 | s2 | s3 | |
| x1 | s1 s’01 | s2 s’11 | s3 s’21 | s3 s’31 |
| x2 | s0 s’02 | s2 s’12 | s0 s’22 | s0 s’32 |
Табл. 3.8
Можно предложить следующий алгоритм перехода от модели автомата Мили к модели Мура:
1. Составить таблицу кодирования состояний автомата Мили.
2. Выписать из таблицы кодирования состояния автомата Мили, соответствующие каждому состоянию множества состояний Мура. В нашем примере:
So=(S’o1;S’o2;S’22;S’32);
S1=S’o1
S2=(S’11;S’12); S3=(S’21;S’31);
Если состояние S’ij входит в множество, соответствующее состоянию Sq, то в колонку таблиц переходов для S’ij следует занести состояние, находящееся в колонке Sq.
3. Функция выходов определяется как F’y(S’ij)=Fy(xi,Sj) при S’ij≠S’o
Для S’o выходной сигнал произвольный.
В нашем примере для состояния S’o выбирается y2, т.к. тогда колонки S’o,S’o2,S’22,S’32 совпадают.
Для того, чтобы отметить выходными сигналами состояния автомата Мура, достаточно наложить таблицу выходов автомата Мили на таблицу кодирования состояний автомата Мура и каждое закодированное состояние отметить тем сигналом, с которым оно совпадает. Обозначим для нашего примера:
S’o2=S’22=S’o; S’o1=S’1; S’12=S’11=S’2;
S’21=S’3; S’31=S’4; S’32=S’5;
В табл. 3.9 приведена совмещенная таблица переходов и выходов автомата Мура, эквивалентного заданному автомату Мили.
| y2 | y2 | y2 | y1 | y2 | y2 | |
| si xj | s’o | s’1 | s’2 | s’3 | s’4 | s’5 |
| x1 | s’1 | s’2 | s’3 | s’4 | s’5 | s’1 |
| x2 | s’0 | s’0 | s’0 | s’5 | s’5 | s’0 |
Табл. 3.9
Так как любой конечный автомат, представимый одной моделью, представим и другой, и так как требуемое количество состояний в модели Мура значительно больше, чем для модели Мили, то использование модели Мура не имеет никаких преимуществ.
Минимизация конечных автоматов.
Если конечный автомат задан конечным входным алфавитом X={x1,x2,…,xn}, конечным выходным алфавитом Y={y1,y2,…,ym} и обладает конечным числом состояний S={s1,s2,…,sk}, то матрица переходов может быть заполнена Knk способами, а матрица выходов mnk способами. Следовательно общее число автоматов с заданными автоматами , насчитывающими n,m,k символов, в точности равно (mk)nk.
При проектировании автомата интерес представляет только зависимость между входным воздействием и выходом автомата, а внутреннее состояние лишь формирует эту функциональную зависимость. Следовательно, любая совокупность состояний, которая обеспечивает указанную зависимость, может быть выбрана в качестве множества состояний. Приведенное выше общее число переходов позволяет обеспечить некоторый выбор при проектировании автомата. Естественно, что такой выбор позволяет обеспечить некоторый выбор при реализации автомата. Естественно, что такой выбор можно осуществлять согласно некоторому критерию. В качестве критерия можно выбрать, например, минимальное число состояний автомата, что ведет к минимизации числа запоминающих элементов, но может привести и к усложнению его комбинационной схемы.
Минимизация числа состояний автоматов тесно связана с понятием эквивалентности автомата. При этом стоит произвести эквивалентные разбиения автомата и объединить полученные эквивалентные состояния.
Если состояния, принадлежащие к одному и тому же классу эквивалентности, дают одну и ту же выходную последовательность, то индивидуальное распознавание каждого состояния становится нецелесообразным.
Для целей минимизации состояний автомата важно распознавание класса эквивалентности, к которому принадлежит каждое состояние. Поэтому всем состояниям автомата, принадлежащим к одному классу эквивалентности, приписывают общее обозначение. Тогда минимальный автомат А1 получается из автомата А путем «объединения» одинаково обозначенных состояний в одно состояние. Способы объединения зависят от способов задания автоматов.
Однако, каким бы способом не была получена минимальная форма конечного автомата, она должна обладать следующими свойствами.
Будем считать, что автомат А1 обладает более минимальной формой, чем автомат А2, если число состояний в автомате А1 меньше или равно числу состояний автомата A2. Если Ак является минимальной формой автомата А, то
А) Ак является единственной минимальной формой с точностью до изоморфизма;
Б) Никакие два состояния в Ак не являются эквивалентными;
В) Не существует автомата эквивалентного А и меньшего чем Ак.
Из этих свойств следует, что если задан какой-либо автомат А, то можно найти минимальный автомат Ак эквивалентный автомату А и являющийся единственным с точностью до изоморфизма. Это значит, что каждый конечный автомат имеет некоторое «каноническое» представление, не зависящее от способа задания исходного автомата. В общем случае существуют способы, которыми автомат может быть описан, и все многообразие описаний может быть сведено к единственному представлению. Такое представление является наиболее компактним по числу используемых состояний.
Синтез конечных автоматов.
Синтез конечного автомата условно можно разделить на два этапа: абстрактный и структурный синтезы.
На этапе абстрактного синтеза выявляют факты изоморфизма автомата, определяют эквивалентные состояния, минимизируют заданный автомат по критерию числа состояний. Вопросы абстрактного синтеза были рассмотрены в предыдущей главе.
На этапе структурного синтеза рассматриваются вопросы элеиентарной базы, на которой происходит синтез заданного автомата, кодирование внутренних состояний автомата, кодирование внутренних состояний и некоторые другие вопросы реализации автоматов.
Наибольшее внимание при структурном синтезе уделяется выбору элементной базе для реализации автомата. В этом смысле задача структурного синтеза конечного автомата заключается в реализации сложного автомата из более простых, называемых элементарными автоматами.