Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. АВТОМАТЫ КАЛАШНИКОВА 100-й СЕРИИ
  2. ЗНАКОМЬТЕСЬ, ЛОТЕРЕЙНЫЕ АВТОМАТЫ
  3. Кофейные торговые автоматы.
  4. Раньше посылают автоматы
  5. РОТОРНЫЕ И РОТОРНО-КОНВЕЙЕРНЫЕ МАШИНЫ-АВТОМАТЫ

Математической моделью дискретного управляющего устройства является абстрактный автомат, который задается множеством из шести Элементов: S = {A, Z, W, , , а1}, где
А = {а1,..., аm,..., аM} - множество состояний (алфавит1 состояний);
Z = {z1,..., zf,..., zF} - множество входных сигналов (входной алфавит);
W = {w1,..., wg,..., wG} - множество выходных сигналов (выходной алфавит);
- функция переходов, реализующая отображение множества D А x Z в А (аs = (аm, zf), аs А);
- функция выходов, реализующая отображение множества D А x Z на W (wg = (аm, zf));
а1 А - начальное состояние автомата.
Автомат2 называется конечным, если конечны множества А, Z, W. В дальнейшем будут рассматриваться только конечные автоматы и термин <конечный> почти всегда будет опускаться. Автомат называется полностью определенным, если Dб = Dл = А x Z. Иными словами, у полностью определенного автомата области определения функции и совпадают со множеством А x Z - множеством всевозможных: пар вида (am, zf). У частичного автомата функции или определены не для всех пар (аm, zf) А x Z.
Понятие состояния в определение автомата введено в связи с тем, что: возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но от некоторой предыстории, т. е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом позволяя устранить время как явную переменную и выразить выходные сигналы, как функцию состояний и входов в данный момент времени.
Абстрактный автомат (рис. 1-1) имеет один входной и один выходной канал. В каждый момент t = 0, 1, 2,... дискретного времени автомат находится в определенном состоянии a (t) из множества А состояний автомата, причем в начальный момент t= 0 он всегда находится в начальном состоянии а (0) = а1. В момент t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал z (t) Z и выдать на выходном канале сигнал w (t) = (а (t), z (t)), переходя в состояние а (t + 1) = (а (t), z(t)); а(t) А, w(t) W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W. Другими словами, если на вход автомата, установленного в начальное состояние а1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2),... -входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2),... - выходное слово. Относя к каждому входному слову соответствующее ему выходное слово, мы получим отображение , индуцированное абстрактным автоматом.


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


На практике наибольшее распространение получили автоматы Мили и Мура Закон функционирования автомата Мили задается уравнениями

a(t+1) = (а(t), z(t)); w(t)= (a(t), z(t)), t = 0,1,2,... (1-1)

а закон функционирования автомата Мура - уравнениями

a(t+1) = (а(t), z(t)); w(t)= (a(t)), t = 0,1,2,...

1 Всякий конечный набор попарно различных символов можно рассматривать как некоторый алфавит, буквы которого - указанные символы Конечную упорядоченную последовательность букв назовем словом в данном алфавите.
2 До главы 2 под термином <автомат> понимается абстрактный автомат.


1.2. Методы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, Z, W, , , а1}, т. е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний необходимо выделить состояние a1, в котором автомат находится в момент t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический и матричный.


1.2.1. Табличный

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

Т 1-1 Общий вид таблицы переходов автомата Мили Т 1-2 Общий вид таблицы выходов автомата Мили

На пересечении столбца аm и строки zf в таблице переходов ставится состояние аs = (аm, zf), в которое автомат переходит из состояния аm под действием сигнала zf, а в таблице выходов-соответствующий этому переходу выходной сигнал wg = (аm, zf). Пример табличного способа задания полностью определенного автомата Мили S1 с тремя состояниями, двумя входными и двумя выходными сигналами приведен в таблицах 1-3 и 1-4.

Т 1-3 Таблица переходов автомата Мили S1 Т 1-4 Таблица выходов автомата Мили S1

Для частичных автоматов, у которых функции или определены не для всех пар (аm, zf) А х Z, на месте неопределенных состояний и выходных сигналов ставится прочерк (частичный автомат S2 задан таблицами 1-5 и 1-6).

Т 1-5 Таблица переходов частичного автомата Мили S2 Т 1-6 Таблица выходов частичного автомата Мили S2

 

Т 1-7 Общий вид отмеченной таблицы переходов автомата Мура Т 1-8 Отмеченная таблица.переходов автомата Мура S2

Так как в автомате Мура выходной сигнал зависит, только от состояния, автомат Мура задается одной отмеченной таблицей переходов (таблица 1-7), в которой каждому ее столбцу приписан, кроме состояния аm, еще и выходной сигнал wg = (аm), соответствующий этому состоянию. Пример табличного описания автомата Мура S3 иллюстрируется таблицей 1-8.


1.2.2. Графический

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.

рис. 1-2 Граф автомата Мили S1 рис. 1-3 Граф автомата Мили S2

Две вершины графа автомата аm и аs (исходное состояние и состояние перехода) соединяются дугой, направленной от аm к аs, если в автомате имеется переход из аm в аs, т. е. если аs = (аm, zf) при некотором zf Z. Дуге (аm, аs) графа автомата приписывается входной сигнал zf и выходной сигнал wg = (аm, zf), если он определен, и ставится прочерк в противном случае. Если переход автомата из состояния аm в состояние а s происходит под действием нескольких входных сигналов, то дуге (аm аs) приписываются все эти входные и соответствующие выходные сигналы. При описании автомата Мура в виде графа выходной сигнал wg = (аm) записывается внутри вершины или рядом с ней. На рис.1-2, 1-3 и 1-4 приведены заданные ранее таблицами графы автоматов S1, S2, S3.


Рис. 1-4. Граф автомата Мили S3

 


1.2.3. Матричный

Матрица соединений автомата есть квадратная матрица , строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент сms= zf / wg, стоящий на пересечении m -ой строки и s -го, в случае автомата Мили соответствует входному сигналу zf, вызывающему переход из состояния аm в состояние аm, и выходному сигналу wg, выдаваемому на этом переходе. Для автомата Мили S1 матрица C1 имеет вид


Если переход из аm в аs происходит под действием нескольких сигналов, элемент сms представляет собой множество пар (вход/выход) для этого перехода, соединенных знаком дизъюнкции. Для модели Мура элемент cms равен множеству входных сигналов на переходе (аm, аs) а выход описывается вектором выходов


m -я компонента которого есть выходной сигнал, отмечающий состояние аm. Для автомата Мура S3


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

Т 1-9 Отмеченная таблица переходов асинхронного автомата Мура S 4


В заключение данного параграфа определим синхронные и асинхронные автоматы. Состояние аs автомата S называется устойчивым состоянием, если для любого входа zf Z, такого, что (аm, zf) = аs, имеет место (аs, zf) = аs.

Автомат S называется асинхронным, если каждое его состояние as A устойчиво. Автомат S называется синхронным, если он не является асинхронным. Необходимо заметить, что построенные на практике автоматы - всегда асинхронные и устойчивость их состоянии всегда обеспечивается тем или иным способом, например введением сигналов синхронизации (см. ниже, § 3-1).


Рис. 1-5. Граф асинхронного автомата Мура S4


Однако на уровне абстрактной теории, когда автомат есть лишь математическая модель, которая не отражает многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными автоматами, что мы и будем делать на протяжении всей данной главы. Пример асинхронного автомата Мура S 4 приведен в табл. 1-9 и на рис. 1-5 Нетрудно видеть, что все его состояния устойчивы.

Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние аs стоит на пересечении строки zf и столбца аm (m<>s), то это состояние аs обязательно должно встретиться в этой же строке в столбце аs. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине as, должна быть петля, отмеченная символами тех же входных сигналов. Анализ таблиц 1-3, 1-5 и 1-8 или рис. 1-2 - 1-4 показывает, что автоматы S1, S2 и S3 являются синхронными.


1.3. Связь между моделями Мили и Мура

1.3.1. Реакция А Мили

В § 1-1 отмечалось, что абстрактный автомат работает как преобразователь слов входного алфавита в слова в выходном алфавите. Остановимся на этом вопросе более подробно, взяв в качестве примера автомат Мили S1 на рис. 1-2 (или табл. 1-3, 1-4). Пусть на вход этого автомата, установленного в начальное состояние, поступает входное слово = z1z1z2z1z2 z2. Так как (a1,z1)=a3, а (a1,z1)=w1,то под действием первой буквы слова - входного сигнала z1 автомат перейдет в состояние а3 и на выходе его появится сигнал w1. Далее, (a3,z1)=a1, (a3,z1)=w 2 и потому при приходе второго сигнала z1 автомат окажется в состоянии a1, а на выходе его появится сигнал w2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову вторая - последовательности состояний, которые проходит автомат под действием букв слова , третья - выходному слову W, которое появляется на выходе автомата:


Назовем W = (а1, ) реакцией автомата Мили в состоянии а1 на входное слово . Как видно из примера, в ответ на входное слово длины k автомат Мили выдает последовательность состояний длины k+1 и выходное слово длины k. В общем виде поведение автомата установленного в состояние аm, можно описать следующим образом:

 


1.3.2. Реакция А Мура

Точно так же можно описать поведение автомата Мура, находящегося в состоянии аm, при приходе входного слова zi1,zi2,:,zik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t(w(t)) зависит лишь от состояния, в котором находится автомат в момент t(а(t)):


Продолжение


Очевидно, что выходной сигнал wi1= (аm) в момент времени i1 не зависит от входного сигнала zi1, а определяется только состоянием а m. Таким образом, этот сигнал w1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние аm, на вход-слово =zi1zi2:zik будем понимать выходное слово той же длины W = (аm, )=wi2wi3:wik+1.


1.3.3. Пример

В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис. 1-6 и найдем его реакцию в начальном состоянии a1 на то же самое входное слово = z1z1z2z1z2z2, которое мы использовали при анализе поведения автомата Мили S1:


Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово с точностью до сдвига на 1 такт совпадают. Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата SA и SB с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.


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

Можно показать [7], что для любого автомата Мили существует эквивалентный ему автомат Мура и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием (a1).
Рассмотрим сначала преобразование автомата Мура в автомат Мили. Пусть дан автомат Мура

SA={AA, ZA, WA, A, A, a1A},


где

AA = {а1,:, аm,:, aM},
ZA= {z1,:, zf,:, zF},
WA = {w1,:, wg,:, wG};


A - реализует отображение AA х Z A в AA, A - отображение A A на WA, а a1A = a1 - начальное состояние.


Рис. 1-6. Граф автомата Мура S5

 


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


Построим автомат Мили

SB={AB, ZB, WB, B , B, a1B},

у которого

AB = AA = {а1,:, аm,:, aM},
ZB= ZA = {z1,:, zf,:, zF},
WB = WA = {w1,:, wg,:, wG};
B = A, a1B = a 1A = a1


Функцию выходов Мили B определим следующим образом. Если в автомате Мура A(am,zf)=as и A(as)=wg, то в автомате Мили B(am,zf)=wg.
Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал (wg), записанный рядом с вершиной (аs), переносится на все дуги, входящие в эту вершину. На рис. 1-8 приведен граф автомата Мили S6, эквивалентного автомату Мура S3 (рис. 1-4).
При табличном способе задания автомата SA таблица переходов автомата SB совпадает с таблицей переходов SA, а таблица выходов SB получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as, в таблице переходов автомата SA.
Из самого способа построения автомата Мили SB очевидно, что он эквивалентен автомату Мура SA. Действительно, если некоторый водной сигнал zf Z поступает на вход автомата SA, находящегося в состоянии аm, то он перейдет в состояние аs= A(аm,zf) и выдаст входной сигнал wg= A(аs). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку B(аm,zf) = A(аm,zf) = аs - и выдаст тот же выходной сигнал wg согласно способу построения функции В. Таким образом, для входной последовательности длины один поведение автоматов SA и SB полностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB, установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.


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

 


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

 


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

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

SA={AA, ZA, WA, A, A, a1A},


где

AA = {а1,:, аm,:, aM},
ZA= {z1,:, zf,:, zF},
WA = {w1,:, wg,:, wG};


A - реализует отображение AA х ZA в AA, A - отображение AA на WA, а a1A = a1 - начальное состояние.
Построим автомат Мура

SB={AB, ZB, WB, B, B, a1B},

у которого

ZB= ZA = {z1,:, zf,:, zF},
WB = WA = {w1,:, wg,:, wG};


Для определения АB каждому состоянию as AA поставим в соответствие множество As всевозможных пар вида (аs,w g), где wg - выходной сигнал, приписанный входящей в аs дуге (рис. 1-9): Аs={(as, wg) | (am, zf) = as и (am, zf) = wg}
Число элементов в множестве Аs равно числу различных выходных сигналов на дугах автомата S A, входящих в состояние as.
Множество остояний автомата SB получим как обединение множеств AS (s=1,:,M):


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


Функции выходов B и переходов B определим слудиющим образом. Каждому состоянию автомата Мура SB, представляющему собой пару вида (as, Wg), поставим в соответствие выходной сигнал Wg. Если в автомате Мили SA был переход а1B (аm, zf) = Wk, то в SB (рис. 1-10) будет переход из множества состояний Am, порождаемых am, в состояние (as, Wk) под действием входного сигнала zf.
В качестве начального состояния а1B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата SA. Напомним, что при сравнении реакции автоматов SA и SB на всевозможные входные слова не должен учитываться выходной сигнал в момент времени t=0, связанный с состоянием а1B автомата SB.


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

Рассомотрим пример преобразования автомата Мили, изображенного на рис. 1-2, в автомат Мура. В автомате Мили Za={Z1, Z2}, Wa={W1, W2}, Aa= {A1,A2,A3}, а1A= а1, A и A определяются графом автомата. В эквивалентном автомате Мура

ZB = ZA = {Z1, Z2}, WB = WA = {W1, W2}.

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

A1={(a1, W1), (a1, W2)} ={b1,b 2};
A2={(a2, W1)}={b3};
A3={(a3, W1) (a3, W2)}={b4 ,b5};
AB=A1U A2U A3={b1,b2,b 3,b4,b5}.

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

B(b1) = B (b3) = B(b4) = W1
B(b2) = B(b5) = W2

3. Рассматривая каждую пару и каждую связь, получим: так как в автомате SA из состояния а1 есть переход под действием сигнала z1 в состояние а3 с выдачей сигнала W1, то из множества A1 = {b1, b2} порождаемых состоянием а1 в автомате Мура SB должен быть переход в состояние {a3, W1}=b4 под действием сигнала z1.

Аналогично с состоянием A1 должен быть переход в состояние {a1, W1} = b1 под действием сигнала z2 и так далее. В качестве начального состояния можно выбрать любую b1,b2 А1. Если сагналы bi заменить на аi, то получим стандартное представление автомата Мура.


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

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

A1U A2U A3={(a2, W1) (a2, W2) (a3, W1) (a3, W2)} = {b2,b3,b4, b5}.

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

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

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

 

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

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 на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые столбцы: 1={b1,b2} b1={a1,a 2,a5,a7,a8} b2={a3,a4,a6, a9,a10,a11,a12}. Действительно, два состояния 1 - эквивалентны, если их реакции на всевозможные входные слова длины 1 совпадают, то есть соответствующие этим состояниям столбцы в таблице выходов должны быть одинаковы.
Строим таблицу 1, заменяя состояния в таблице переходов соответствующими классами 1 -эквивалентности.

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

Очевидно, что 1 -эквивалентные состояния аm и аs будут 2 - эквивалентными, если они переводятся любым входным сигналом также в 1 - эквивалентные. По таблице 1-12 получаем разбиение 2={C1,C2,C3,C 4}; C1= {a1,a2}, C2={a5,a7,a8 }, C3={a3,a4,a6,a9,a11}, C4= {a10,a12}.

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

Аналогично построим 3 ={D1,D2,D3,D4, D5}; D1={a1,a2}, D2={a5,a7}, D3={a8}, D4={a3,a4,a6,a9,a11 }, D5={a10,a12} и, наконец 4 ={E1,E2,E3,E4,E5}, которое совпадает с 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 = {B1, B2, B3}.

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={a1,:,am,:,aM} - множество состояний;
Z={z1,:, zf,:,zF} - множество входных сигналов;
W={w1,:,wg,:,wG} - множество выходных сигналов типа 1;
U={u1,:,uh,:,uH} - множество выходных сигналов типа 2;
a1 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,:

Выходной сигнал uh = 2(аm) выдается все время, пока автомат находится в некотором состоянии аm. Выходной сигнал wg = 1(am, zf) выдается во время действия входного сигнала zf при нахождении автомата в состоянии а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-12-08; просмотров: 241 | Нарушение авторских прав

mybiblioteka.su - 2015-2024 год. (0.05 сек.)