Автоматы Мили и Мура 2 страница

Рис. 1-8. Автомат Мили S₆эквивалентный автомату Мура S₅

Рис. 1-9. Построение множества A_s

1.3.5. Переход от А Мили к А Мура

Прежде чем рассмотреть трансформацию автомата-Мили в автомат Мура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу (пример - состояние a₁ на рис. 1-3). Итак, пусть задан автомат Мили

S_A={A_A, Z_A, W_A, _A, _A, a_1A},

где

A_A = {а₁,:, а_m,:, a_M},
Z_A= {z₁,:, z_f,:, z_F},
W_A = {w₁,:, w_g,:, w_G};

_A - реализует отображение A_A х Z_A в A_A, _A - отображение A_A на W_A , а a_1A = a₁ - начальное состояние.
Построим автомат Мура

S_B={A_B, Z_B, W_B, _B, _B, a_1B},

у которого

Z_B= Z_A = {z₁,:, z_f,:, z_F},
W_B = W_A = {w₁,:, w_g,:, w_G};

Для определения А_B каждому состоянию a_s A_A поставим в соответствие множество A_s всевозможных пар вида (а_s,w _g), где w_g - выходной сигнал, приписанный входящей в а_s дуге (рис. 1-9): А_s={(a_s, w_g) | (a_m, z_f) = a_s и (a_m, z_f) = w_g}
Число элементов в множестве А_s равно числу различных выходных сигналов на дугах автомата S _A, входящих в состояние a_s.
Множество остояний автомата S_B получим как обединение множеств A_S (s=1,:,M):

Рис. 1-10. Иллюстрация перехода от модели Мили к модели Мура

Функции выходов _B и переходов _B определим слудиющим образом. Каждому состоянию автомата Мура S_B, представляющему собой пару вида (a_s, W_g), поставим в соответствие выходной сигнал W_g. Если в автомате Мили S_A был переход а1_B (а_m, z_f) = W_k , то в S_B (рис. 1-10) будет переход из множества состояний A_m, порождаемых a_m, в состояние (a_s, W_k) под действием входного сигнала z_f.
В качестве начального состояния а1_B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата S_A. Напомним, что при сравнении реакции автоматов S_A и S_B на всевозможные входные слова не должен учитываться выходной сигнал в момент времени t=0, связанный с состоянием а1_B автомата S_B .

1.3.6. Пример преобразования автомата Мили в автомат Мура

Рассомотрим пример преобразования автомата Мили, изображенного на рис. 1-2, в автомат Мура. В автомате Мили Z_a={Z₁, Z₂}, W_a={W₁, W₂}, A_a= {A₁,A₂,A₃}, а1_A= а1, _A и _A определяются графом автомата. В эквивалентном автомате Мура

Z_B = Z_A = {Z₁, Z₂}, W_B = W_A = {W₁, W₂}.

1. Построим множество A_B, для чего найдем множество пар, порождаемых каждым состоянием автомата S_A:

A₁={(a₁, W₁), (a₁, W₂)} ={b₁,b ₂};
A₂={(a₂, W₁)}={b₃};
A₃={(a₃, W₁) (a₃, W₂)}={b₄ ,b₅};
A_B=A₁U A₂U A₃={b₁,b₂,b ₃,b₄,b₅}.

2. C каждым состоянием, представляющем собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:

_B(b₁) = _B (b₃) = _B(b₄) = W_1
B(b₂) = _B(b₅) = W₂

3. Рассматривая каждую пару и каждую связь, получим: так как в автомате S_A из состояния а1 есть переход под действием сигнала z₁ в состояние а₃ с выдачей сигнала W₁, то из множества A₁ = {b₁, b₂} порождаемых состоянием а1 в автомате Мура S_B должен быть переход в состояние {a₃, W₁}=b₄ под действием сигнала z₁.

Аналогично с состоянием A₁ должен быть переход в состояние {a₁, W₁} = b₁ под действием сигнала z₂ и так далее. В качестве начального состояния можно выбрать любую b₁,b₂ А₁. Если сагналы b_i заменить на а_i, то получим стандартное представление автомата Мура.

1.3.7. Пример перехода от автомата Мили с переходящим состоянием к автомату Мура

Рассмотрим переход от автомата Мили к автомату Мура, у которого входное состояние является переходящим. Будем составлять множество состояний следующим образом:

A₁U A₂U A₃={(a₂, W₁) (a₂, W₂) (a₃, W₁) (a₃, W₂)} = {b₂,b₃,b₄, b₅}.

К этим состояниям добавим пару (а₁, -) = b₁. Где " - " означает, что выходной сигнал в состоянии b₁ не определен. Функцию переходов S_B будем определять как и раньше.
Из данного графа получим граф:

В качестве начального состояния автомата Мура можно взять порождаемое им состояние.
Эквивалентность автоматов S_B и S_A при преобразовании автомата Мили в автомат Мура на множестве входных слов конечной длины легко доказать по индукции подобно изложенному выше при обратном преобразовании.

Методы взаимной транспозиции автоматов Мили и Мура показывают, что при переходе от автомата Мили к автомату Мура число состояний принципиально не меняется. В то время как при обратном переходе в автомат Мура число состояний, как правило, увеличивается. Вследствие транзитивности отношения эквивалентности два автомата Мили, первый из которых получен из автомата Мура, так же будут эквивалентны, но у второго автомата число состояний будет больше. Таким образом эквивалентные между собой автоматы могут иметь различное число состояний. В связи с чем и возникает задача нахождения минимального автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.

1.4. Минимизация полностью определенных автоматов

1.4.1. Теоретические основы минимизации

Рассмотрим алгоритм минимизации полностью определенных абстрактных автоматов Мили, предложенный Ауфенкампом и Хоном. Основная идея этого метода состоит в разбиении всех состояний исходного абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Таким образом, получающийся в результате минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Два состояния автомата а_m и а_s называются эквивалентными а_m ~ а_s, если (а_m, ) = (а_s, ) для всевозможных входных слов . Если а_m и а_s не эквивалентны, они различимы. Более слабой эквивалентностью является k - эквивалентность.
Состояния а_m и а_s k -эквивалентны а_m ~ а_s , если (а_m, _k) = (а_s, _k) для всевозможных входных слов _k длины k.
Если состояния не k -эквивалентны, они k -различимы. Введенные отношения эквивалентности и k - эквивалентности рефлексивны, симетричны, транзитивны. Следовательно, они являются отношениями эквивалентности и могут быть использованы для разбиения множества А состояний автомата на попарно не пересекающиеся классы. Соответствующие разбиения на класы эквивалентных и k -эквивалентных состояний будем обозначать и k. Разбиение позволяет определить избыточные элементы в множестве состояний А. Пусть, например, а_m и а_s эквивалентны. Это значит, что сточки зрения реакций автомата на всевозможные входные слова неважно, находится автомат в состоянии а_m или а_s, и одно и них, например а_s , может быть удалено из множества А. Если каждый класс эквивалентности содержит только одно состояние, множество А несократимо. Если же один или несколько класов содержат более одного элемента, все элементы, кроме одного в каждом класе, могут быть исключены из множества А, в результате чего получается автомат с минимальным числом состояний.

1.4.2. Алгоритм минимизации

Пусть автомат S = {A, Z, W, , , а1} подвергается минимизации. Этот процесс состоит из:

1. Находятся последовательные разбиения 1, 2,:, k, k+1 множества А на классы одно-, двух-,:, k-, k+1 эквивалентных состояний, до тех пор пока на каком-то k+1 шаге не окажется, что k+1= k. Нетрудно показать, что тогда разбиение k = , то есть что k- эквивалентные состояния являются в этом случае эквивалентными и число шагов k, при котором k = не превышает М-1, где М - число элементов в множестве А.

2. В каждом классе эквивалентности разбиения выбираются по одному элементу, которые образуют множество А' состояний минимального автомата S' = {A', Z, W, , , а'1}, эквивалентного автомату S.

3. Функции переходов ' и ' автомата S' определяются на множестве A' x Z. Для этого в таблице переходов и выходов вычеркиваются столбцы, соответсвующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества A'.

4. В качестве а'1 выбирается одно из состояний, эквивалентное состоянию а1. В частности, удобно за а'1 принимать само а1.

1.4.3. Пример минимизации автомата Мили

T1-10.Таблица переходов не минимального автомата Мили

T1-11. Таблица выходов не минимального автомата Мили

Непосредственно по таблице выходов получаем разбиение 1 на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые столбцы: ₁={b₁,b₂} b₁={a₁,a ₂,a₅,a₇,a₈} b₂={a₃,a₄,a₆, a₉,a₁₀,a₁₁,a₁₂}. Действительно, два состояния 1 - эквивалентны, если их реакции на всевозможные входные слова длины 1 совпадают, то есть соответствующие этим состояниям столбцы в таблице выходов должны быть одинаковы.
Строим таблицу 1, заменяя состояния в таблице переходов соответствующими классами 1 -эквивалентности.

T1-12.Разбиение 1 состояний автомата Мили.

Очевидно, что 1 -эквивалентные состояния а_m и а_s будут 2 - эквивалентными, если они переводятся любым входным сигналом также в 1 - эквивалентные. По таблице 1-12 получаем разбиение ₂={C₁,C₂,C₃,C ₄}; C₁= {a₁,a₂}, C₂={a₅,a₇,a₈ }, C₃={a₃,a₄,a₆,a₉,a₁₁}, C₄= {a₁₀,a₁₂}.

T1-13.Разбиение 2 состояний автомата Мили.

Аналогично построим 3 ={D₁,D₂,D₃,D₄, D₅}; D₁={a₁,a₂}, D₂={a₅,a₇}, D₃={a₈}, D₄={a₃,a₄,a₆,a₉,a₁₁ }, D₅={a₁₀,a₁₂} и, наконец 4 ={E₁ ,E₂,E₃,E₄,E₅}, которое совпадает с 3. Процедура разбиения завершена. Разбиение 3 есть разбиение множества состояний автомата Мили на классы эквивалентных между собой состояний.

T1-14.Разбиение 3 состояний автомата Мили.

Вычеркиваем из D1 а2, из D2 а7, из D4 а4, а6, а9, а11, из D5 а12 определяем минимальный автомат Мили.

T1-15.Таблица переходов минимального автомата Мили.

T1-16.Таблица выходов минимального автомата Мили.

1.4.4. Пример минимизации автомата Мура

При минимизации автоматов Мура вводится понятие 0 -эквивалентности состояний и разбиение множества состояний на 0 -классы: 0 -эквивалентными называются любые одинаково отмеченные состояния автоматов Мура. Если два 0 -эквивалентных состояния любым входным сигналом переводится в два 0 -эквивалентных состояния, то они назаваются 1 -эквивалентными. Все дальнейшие классы эквивалентности состояний для автоматов Мура определяются аналогично приведенному выше для автоматов Мили.

T1-17. Отмеченная таблица переходов неминимального автомата Мура.

В результате применения алгоритма минимизации к автомату Мура, имеющему 12 состояний, получим автомат Мура, имеющий 4 состояния. Отпуская промежуточные таблицы, приведем лишь последовательность разбиений: 0 = {B₁, B₂, B₃}.

T1-18. Отмеченная таблица переходов минимального автомата Мура.

B1={a1, a2, a8}; B2={a6, a9, a10, a11, a12}; B3={a3, a4, a5, a7}
1 ={C1, C2, C3, C4}.
C1={ a1, a2, a8}; C2={ a6, a9, a11}; C3={ a10, a12}; C4={ a3, a4, a5, a7}
2 ={D1, D2, D3, D4};
2 = 1;
D1 = C1; D2 = C2; D3 = C3; D4 = C4.

1.5. Совмещенная модель автомата (С- автомат)

Под абстрактным С -автоматом будем понимать математическую модель дискретного устройства, определяемую множеством из 8 элементов

S={A, Z, W, U, a1, , 1, 2},где

A={a₁,:,a_m,:,a_M} - множество состояний;
Z={z₁,:, z_f,:,z_F} - множество входных сигналов;
W={w₁,:,w_g,:,w_G} - множество выходных сигналов типа 1;
U={u₁,:,u_h,:,u_H} - множество выходных сигналов типа 2;
a₁ A - начальное состояние;
- функция переходов, реализующая отображение множества D A x Z в A;
1 - функция выходов, реализующая отображение множества D 1 A x Z на W;
2 - функция выходов, реализующая отображение множества D 2 A на U.

Рис. 1-14. Абстрактный автомат.

Абстрактный С -автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С -автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. С -автомат можно описать следующими уравнениями:

a(t+1)= (a(t), z(t)); w(t)= 1(a(t), z(t)); u(t)= 2(a(t)), t=0,1,2,:

Выходной сигнал u_h = 2(а_m) выдается все время, пока автомат находится в некотором состоянии а_m. Выходной сигнал w_g = 1(a_m, z_f) выдается во время действия входного сигнала z_f при нахождении автомата в состоянии а_m. Очевидно что от С -автомата легко перейти к автоматам Мили или Мура, так же как возможна трансформация автомата Мили в автомат Мура и наоборот. Для создания С -автоматов будем также использовать табличный и графический методы. В первом случае таблица переходов (табл. 1-19) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим ему сигналом типа 2 (табл. 1-20). При задании С -автомата в виде графа сигналы типа 1 будем приписывать дугам графа рядом с входными сигналами, а сигналы типа 2- вершинам- состояниям, которым они соответствуют.

Нетрудно показать, что к полностью определенному С -автомату можно применить алгоритм минимизации Ауфенкампа- Хона, если под одноэквивалентными понимать состояния, которые одинаково отмечены и имеют одинаковые столбцы в таблице выходов. Проводя последовательность разбиений на 1-, 2-,:, k-, k+ 1 - эквивалентные классы до совпадения разбиений k+ 1 и k получим разбиение множества состояний на эквивалентные, после чего замена каждого класса эквивалентности одном состоянием дает минимальный С -автомат. В результате применения такого алгоритма к автомату, заданному таблицами 1-21 и 1-22, получим минимальный С -автомат, представленный в таблице 1-23 и 1-24. Опуская промежуточные таблицы, приведем лишь последовательность разбиений при минимизации:

Дата добавления: 2015-05-09