Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Абстрактные автоматы

1.1. Определение абстрактного автомата
1.2. Методы задания автоматов
1.2.1. Табличный
1.2.2. Графический
1.2.3. Матричный
1.3. Связь между моделями Мили и Мура
1.3.1. Реакция А Мили
1.3.2. Реакция А Мура
1.3.3. Пример
1.3.4. Переход от А Мура к А Мили
1.3.5. Переход от А Мили к А Мура
1.3.6. Пример преобразования автомата Мили в автомат Мура
1.3.7. Пример перехода от автомата Мили с переходящим состоянием к автомату Мура
1.4. Минимизация полностью определенных автоматов
1.4.1. Теоретические основы минимизации
1.4.2. Алгоритм минимизации
1.4.3. Пример минимизации автомата Мили
1.4.4. Пример минимизации автомата Мура
1.5. Совмещенная модель автомата (С-автомат)

 

1.1. Определение абстрактного автомата

Математической моделью дискретного управляющего устройства является абстрактный автомат, который задается множеством из шести Элементов: 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= Am,zf) и выдаст входной сигнал wg= As). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку Bm,zf) = Am,zf) = аs- и выдаст тот же выходной сигнал wg согласно способу построения функции В. Таким образом, для входной последовательности длины один поведение автоматов SA и SB полностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB , установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.





Дата добавления: 2015-05-09; Просмотров: 1368; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.81.152.30
Генерация страницы за: 0.191 сек.