Тема 3. Переход от одной модели автомата к другой: обоснование возможности и практика

Переход от модели Мили к модели Мура.

Запишем уравнение функции выходов автомата Мили:

Так как КА один и тот же, та же функция выходов в случае модели Мура описывается уравнением:

(индексы ^Ми и ^Му введены для наглядности). Следовательно, имеет место соответствие аргументов:

Если данное соответствие рассмотреть для момента времени (t+1), получим:

Таким образом, зная функцию переходов автомата Мили f_s^Ми, можно перейти к функции переходов автомата Мура f_s^Му.

‚Переход от модели Мура к модели Мили.

Поставим в соответствие некоторому состоянию автомата Мура в момент времени (t-1) состояние автомата Мили в момент времени t:

Для y(t) имеем:

Используя соответствие (*), получаем аргументы функции выходов автомата Мили: (x(t), s(t)). Но

Таким образом, зная f_y^Му и f_s^Му, можно перейти к f_y^Ми. Для функции выходов возможность перехода обоснована.

Для s(t+1), используя соответствие (*), имеем:

Но пара (x(t), s(t)) является аргументом функции переходов автомата Мили:

Следовательно, зная f_s^Му, можно перейти к f_s^Ми. Итак, для функции f_s возможность перехода также обоснована.

На основании изложенного можно утверждать, что модели Мили и Мура функционально эквивалентны. Автомат, рассматриваемый как «черный ящик», будет одинаково реагировать на входные сигналы независимо от того, какая модель реализована – Мили либо Мура. Иными словами, переход от одной модели КА к другой не влияет на результат преобразования автоматом слов входного алфавита.

Дадим определение. Два автомата с одинаковыми входными и выходными алфавитами X и Y называются эквивалентными, если после установки обоих в начальное состояние их реакции на каждое входное слово совпадают.

В теории автоматов доказывается следующее утверждение.

Лемма. Для каждого конечного автомата Мили может быть построен эквивалентный ему конечный автомат Мура, и наоборот.

На практике от автомата Мура к автомату Мили можно просто и наглядно перейти в случае представления автомата графом переходов. Каждому состоянию автомата Мура (вершине графа КА Мура) ставится в соответствие одно состояние автомата Мили (вершина графа КА Мили). Таким образом, получаем граф КА Мили, изоморфный исходному графу КА Мура, переходы между состояниями сохраняются. Каждый выходной сигнал КА Мура, записанный рядом со своей вершиной, переносим на все дуги графа КА Мили, входящие в соответствующую ей вершину. Пример показан на рис. 2.6. Таблицы переходов/выходов для обеих моделей в данном примере очевидны.

Алгоритм обратного перехода более сложен, поскольку в каждом состоянии s_i' автомата Мура вырабатывается выходной сигнал одного и только одного значения y_i, а в автомате

Рис. 3.1. Простой переход от автомата Мура к автомату Мили

Мили это совсем необязательно. По этой причине приходится вводить состояния автомата Мура, соответствующие каждой паре «состояние – входной сигнал» автомата Мили. Из этого следует, что эквивалентные автоматы разных моделей имеют, вообще говоря, различное число состояний, то есть в общем случае для одного и того же КА |S^Ми| ≠ |S^Му|.

Алгоритм перехода от автомата Мили к автомату Мура рассмотрим на следующем примере.

Автомат задан описанием: «двоичные цифры 0 и 1 подаются на вход КА, который циклически по модулю 3 считает накопленное число единиц».

Модель Мили заданного автомата, полученная в результате абстрактного синтеза, представлена на рис. 3.2 и рис. 3.3 графом переходов и таблицей переходов/выходов соответственно. Пояснение:

X = {0, 1};

Y = {0, 1, 2} (значения соответствуют числу принятых единиц);

S = {s₀, s₁, s₂} (автомат хранит: s₀ – ноль единиц, s₁ – одну единицу, s₂ – две единицы).

Рис. 3.2. Граф переходов КА

y(t)	s(t+1)
x(t) s(t)
s0			s0	s1
s1			s1	s2
s2			s2	s0

Рис. 3.3. Таблица переходов/выходов КА

Выполним переход от полученного КА Мили к эквивалентному ему КА Мура.

Шаг 1. Каждой паре «состояние s_i – входной сигнал x_j» автомата Мили ставим в соответствие состояние s_ij автомата Мура. Формально вводим начальное состояние автомата Мура s₀'. В результате формируется подтаблица состояний автомата Мура (рис. 3.4):

s'(t)	s(t+1)
x(t) s(t)			0
s0 = s0'	s00	s01	s0	s1
s1	s10	s11	s1	s2
s2	s20	s21	s2	s0

Подтаблица состояний Подтаблица переходов

автомата Мура автомата Мили

Рис. 3.4. Подтаблица состояний КА Мура, соединенная с подтаблицей переходов КА Мили

Шаг 2. Из полученной таблицы выписываем состояния автомата Мили и соответствующие им состояния автомата Мура (например, состоянию s₀ соответствуют s₀₀, s₂₁ и, формально, s₀': на рис. 3.4. показано круглыми пунктирными выносками). Получаем:

Шаг 3. Составляем таблицу переходов автомата Мура. Сначала выписываем в ряд все состояния автомата Мура. Затем заполняем столбцы для каждого значения входного сигнала, руководствуясь правилом: если состояние s_ij входит в множество для состояния s_p КА Мили (шаг 2), то в столбец для s_ij включаются те состояния из подтаблицы состояний КА Мура (рис. 3.4), которые входят в строку s_p.

К примеру, состояние s₁₁ КА Мура входит в множество для состояния s₂ КА Мили (см. шаг 2). Значит, в столбец для s₁₁ войдут состояния s₂₀ для x = 0 и s₂₁ для x = 1. В таблице на рис. 3.4 это соответствие показано прямоугольной пунктирной выноской.

В последнюю очередь для каждого состояния автомата Мура проставляются значения выходного сигнала:

Например,

Для состояния s₀' обычно полагают такое же значение выходного сигнала, как для s₀₀. Полученная таблица переходов КА Мура показана на рис. 3.5.

y(t)
sij(t) x(t)	s0'	s00	s01	s10	s11	s20	s21
	s00	s00	s10	s10	s20	s20	s00
	s01	s01	s11	s11	s21	s21	s01

s_ij(t+1)

Рис. 3.5. Таблица переходов КА Мура

Шаг 4. Из таблицы переходов, полученной на предыдущем шаге, видно, что среди состояний автомата есть такие, которым соответствуют: а) одни и те же значения выходного сигнала и б) переходы в одни и те же состояния при любых входных воздействиях. Это так называемые эквивалентные состояния. Например, состояния s₀₀ и s₂₁ – эквивалентные, так как автомат, находясь в каждом из них, переходит в состояния s₀₀ и s₀₁ при x = 0 и x = 1 соответственно и выдает сигнал y = 0. Эквивалентные состояния неотличимы, поэтому имеет смысл оставить только одно из них. Процесс выявления и удаления эквивалентных состояний называется минимизацией автомата. В данном примере имеем три группы эквивалентных состояний:

{s₀', s₀₀, s₂₁}; {s₀₁, s₁₀}; {s₁₁, s₂₀}.

Введем новые обозначения состояний:

s₀' = s₀' = s₀₀ = s₂₁;

s₁' = s₀₁ = s₁₀;

s₂' = s₁₁ = s₂₀.

Шаг 5. Строим окончательную таблицу переходов/выходов и граф автомата Мура (рис. 3.6 и 3.7):

y(t)
s'(t) x(t)	s0'	s1'	s2'
	s0'	s1'	s2'
	s1'	s2'	s0'

s'(t+1)

Рис. 3.6. Окончательная таблица переходов КА Мура

Рис. 3.7. Граф полученного КА Мура

Обратим внимание, что граф переходов изоморфен графу автомата Мили, что в общем случае совсем необязательно. В данном примере изоморфизм объясняется заданием множеств S и Y на этапе абстрактного синтеза. Обычно автомат Мура имеет большее число состояний, чем исходный автомат Мили.

Контрольные вопросы.

1. Каков круг задач, решаемых в теории автоматов?

2. Что такое абстрактный автомат?

3. Какие существуют виды абстрактных автоматов (по трем классификационным признакам)?

4. Что такое конечный автомат? Каковы характеристические функции конечного автомата?

5. Какие существуют способы задания конечного автомата?

6. Каковы основные модели конечных автоматов? В чем их сходство и различие?

7. Обоснуйте принципиальную возможность перехода от одной модели конечного автомата к другой.

8. В чем состоит алгоритм перехода от автомата Мили к автомату Мура? Как выполнить обратный переход?

Дата добавления: 2015-07-26; просмотров: 365; Нарушение авторских прав

Мы поможем в написании ваших работ!