В предыдущей статье были рассмотрен автомат Мили и его программная реализация.
Автоматы Мура образуют другой класс моделей, с точки зрения вычислительной мощности полностью эквивалентный классу автоматов Мили.
Итак, рассмотрим еще один тип конечноавтоматного преобразователя информации: Автомат Мура.
В автомате Мура:
A = <S,X,Y,s0,δ,λ>, выходная функция
λ определяется не на паре
<состояние, входной сигнал>, а только на состоянии.
Выход Автомата Мура определяется однозначно тем состоянием, в которое автомат переходит после приема входного сигнала.
ПРИМЕР:
Зададим КА Мура, который будет являться эквивалентным Автомату Мили, рассмотренному в предыдущей статье.
Не составит труда его преобразовать.
На графе автомата Мили легко прослеживается взаимосвязь элементов входного и выходного алфавитов.
Построив таблицу соответствий состояний автомата Мили алфавитным парам, легко увидеть какие состояния требуют расщепления.
Состояния
s2 и
s3 Автомата Мили расщепляется на два эквивалентных состояния
s2 = {s2, s4}, s3={s3, s5}, с каждым из которых связывается один выходной символ.
Автомат Мура будет иметь:
шесть состояний,
S = {s0, s1, s2, s3, s4, s5}.
два входных сигнала
X = {x0, x1}, где: x0 = 0, x1 = 1.
шесть выходных сигналов
Y = {y0, y1, y2, y3, y4, y5} где: y0 = 1, y1 = 2, y2 = 3, y3 = 4, y4 = 5, y5 = 6.
Теперь представим автомат Мура в виде графа (в сравнении с автоматом Мили):
РЕАЛИЗАЦИЯ КА Мура
Для программной реализации автомата будет использоваться язык C# и технология WWF.
На рисунке 1 представлена блок-схема программы, реализующей поведение автомата Мура.
Нетрудно увидеть, что топология блок-схемы программы повторяет топологию графа переходов конечного автомата.
С каждым состоянием связана операция, выполнения определенных действий при наступлении данного состояния, ожидания прихода нового входного сигнала, чтение его в стандартный буфер –
int x; , а также последующий анализ того, какой это сигнал и перевод автомата в новое состояние.
(см. Рисунок 2)
Данная программная модель автомата Мура, полностью эквивалентна модели автомата Мили представленной в предыдущей статье.
Автор: Александр Шевчук