Antik (1082243), страница 4
Текст из файла (страница 4)
Или иначе, если автомат Мили минимален, т.е. все N состояний автомата неэквивалентны, то длялюбой пары состояний существует входная последовательностьдлины не более N-1, различающая эти состояния.20Причем граница N-1 в общем случае не улучшаема см.рис.15 и рис.16.Рис.15. Автомат, у которого все состояния эквивалентны1/ 110/ 01/ 020/ 01/ 00/ 0n-11/ 00/ 01/ 0n0/ 0Рис.16.
Автомат, у которого нет эквивалентных состояний, а дляразличения неэквивалентности состояний с номерами n и(n-1) необходима последовательность длины n-1Для автомата Мура эта же оценка равна N-L, где L – числовыходных символов.Достаточным условием эквивалентности состояний являетсясовпадение соответствующих им строк в автоматной таблице.Такие состояния называют явно эквивалентными.Необходимым условием эквивалентности состояний является совпадение выходных значений.
Если в строках совпадаюттолько выходные значения, то состояния, соответствующие этимстрокам эквивалентны при эквивалентности новых состояний вэтих строках.За один просмотр таблицы нельзя определить в общем случае все эквивалентные состояния. Для этого нужна процедура повторных просмотров таблицы, сходящаяся к замкнутому разбиению множества состояний на классы эквивалентности. Разбиениезамкнуто, если для любого состояния из одного класса эквивалентности при подаче одинакового входного воздействия автоматпереходит снова в состояния из одного класса эквивалентности.Процедуру минимизации опишем в виде алгоритма, основанного на последовательном применении необходимого условияэквивалентности. (Гилл - Введение ...
с. 90-92, 3.6).1) Явно эквивалентные между собой состояния заменяются21одним состоянием.2) Состояниям с одинаковой комбинацией выходных значений присваивается один и тот же префикс. Таблица переписывается.3) Состояниям с одинаковой комбинацией (выход, префикс)присваивается один и тот же префикс. Таблица переписывается.Условие перехода: если количество различных префиксов неувеличилось или равно числу состояний, то переход к пункту 4,иначе повторяется пункт 3.4) Различных классов эквивалентности столько же, сколькоразличных префиксов. Каждому классу эквивалентности в минимальном автомате сопоставляется одно состояние.Пример 6.2-1.
Автомат Мура, заданный табл.1. После первойитерации (табл.2) получаем табл.3 минимального автомата.1234Таблица-1выход 01211040313412A-1A-2B-3B-4Таблица-2выход01A-21A-10B-40B-31B-3B-4A-4A-2Таблица-3выход 0 1A1A BB0B AПример 6.2-2. Автомат Мили, заданный табл.1. Строки автоматной таблицы - входные символы, столбцы - состояния. В результате четырех итераций (табл.2) окончательно получаем таблицуминимального автомата (табл.3).шаг-0abcшаг-1abcшаг-2abc11,20,20,4A-11,B-20,B-20,A-4A-11,B-20,B-20,A-420,11,31,3B-20,A-11,B-31,B-3B-20,A-11,B-31,B-330,11,21,2B-30,A-11,B-21,B-2B-30,A-11,B-21,B-241,50,30,3A-41,B-50,B-30,A-1A-41,B-50,B-30,A-150,71,81,5B-50,A-71,B-81,B-5B-50,A-71,C-81,B-561,50,20,7Таблица-171,30,30,680,71,61,6A-61,B-50,B-20,A-7A-61,B-50,B-20,A-7Таблица-2A-71,B-30,B-30,A-6A-71,B-30,B-30,A-6B-80,A-61,B-81,A-6C-80,A-61,C-81,A-622шаг-3abcшаг-4abcшаг-5A-11,B-20,B-20,A-4A-11,B-20,B-20,E-4AB-20,A-11,B-31,B-3B-20,A-11,B-31,B-3Babc6.3.B-30,A-11,B-21,B-2B-30,A-11,B-21,B-2BAB1,B0,B0,E0,A1,B1,BA-41,D-50,B-30,A-1E-41,D-50,B-30,A-1ED-50,A-71,C-81,D-5D-50,A-71,C-81,D-5DТаблица-3CD0,E1,C1,E0,A1,C1,DA-61,D-50,B-20,A-7E-61,D-50,B-20,A-7EA-71,B-30,B-30,A-6A-71,B-30,B-30,E-6AC-80,A-61,C-81,A-6C-80,E-61,C-81,E-6CE1,D0,B0,AЭквивалентность автоматов Мура автоматам Мили6.3.1.
На практике бывает удобно перейти к эквивалентномуавтомату, имеющему, быть может, большее число состояний, чемисходный автомат, но зато обладающему некоторыми другими“полезными” качествами.a) автомат Мура МΛ с регистром–развязкой на выходеб) автомат Мура МVс регистром–развязкой на входеРис.17. Автоматы МураТак обстоит дело при переходе от произвольно заданногоавтомата Мили к эквивалентному ему автомату Мура, который23обладает “полезным” свойством “развязывать” вход и выход. Втаких случаях вместо склеивания состояний применяется в некотором смысле обратная операция “расщепления состояний”.Автомат Мура, полученный как эквивалентный автоматуМили, выдает такие же выходные последовательности, но сосдвигом на такт, а значит выходом в начальный момент временинеобходимо пренебречь.На структурном уровне получение эквивалентного автоматаМура может выглядеть довольно просто, как некоторое структурирование памяти автомата - рис.17.Преобразование автомата Мили в эквивалентный ему автомат Мура покажем на следующем примере.Пример 6.3.-1.
Инкрементор - рис.18. Автомат Мили.Рис.18. Таблица и диаграмма автомата МилиВ первом случае (рис.17a), состоянию si в автомате M (Мили), сопоставляется множество состояний {sij[bj]} автомата MΛ(Мура), если есть переходы в si с выходом bj (si:=g(x, аk/bj),Функция переходов gΛ определяется следующим образом, еслиsq:=g(si, аk/bp), то sqp:=gΛ(sij,аk) для каждого j.Если автомат M инициальный с начальным состоянием so,то в автомате MΛ начальным может быть любое состояние soi.Если среди возможных начальных состояний автомата MΛ естьсостояние без входящих дуг, то такое состояние эквивалентнолюбому другому из возможных начальных, а его выходное значение не определено.s/ba01С0 0D1 C0D0 0D0 D1D1 1D0 D1C 0 /010D 1 /10101D 0 /0Рис.19.
Таблица и диаграмма автомата Мура МΛ24Во втором случае (рис.17б), каждой паре (аj,si) автомата M(Мили) сопоставляется состояние sji автомата MV (Мура).Функция sq:=g(si,аj) трансформируется вфункцию skq:=gV(sji,аk), для каждого k.Функция bp=f(si,аj) трансформируется вфункцию bp=fV(sji).Если автомат M инициальный с начальным состоянием so,то в автомате MV из всех состояний sio надо выбрать любое состояние с петлей (sio:=gV(sio,аi)) и сделать его начальным, если такого нет, то начальным может быть любое состояние sio.Рис.20. Таблица и диаграмма автомата Мура МVМинимальный автомат для того и другого случая конечноодин и тот же (рис.21).a 0 1sK 0 L KL 1 N LN 0 N L1K/ 0 0L/ 1 101N/ 0 0Рис.21. Таблица и диаграмма минимального автомата Мура6.3.2.
При замене автомата Мура равносильным ему автоматом Мили, сопоставляем каждой дуге di[ak], направленной к вершине sz[bh] в автомате Мура дугу di[ak/bh], направленную к вершине sz в автомате Мили.7.Автоматы распознавания языковСинхронный автомат (любой) можно рассматривать как25устройство, распознающее некоторое множество Q слов конечной длины (само множество Q может быть бесконечным). Будемназывать множество Q языком. Множество Q называют такжесобытием - термином, который при проектировании может вызвать полезные ассоциации.
Если во входной последовательностисимволов (букв) поступает слово, принадлежащее языку, то автомат выдает символ-индикатор этого языка.Языки (события), которые синхронный автомат способенраспознать, называют регулярными (распознаваемыми, автоматными,определимыми,допускаемыми,разрешимыми,представимыми, рациональными).В автоматном графе инициального автомата всем событиямсоответствуют те слова, которые переводят автомат из начального состояния к дугам или вершинам, помеченным выходнымсимволом-индикатором.Можно считать, что автономные автоматы способны распознавать слова только в однобуквенном алфавите. Распознаваемыйавтономным автоматом язык состоит из слов определенной длины.7.1.
Регулярные языкиПонятие “язык Q - регулярен” означает, что можно построить СЦА, распознающий язык Q.Любое конечное множество слов конечной длины распознаваемо СЦА. В тоже время не всякий бесконечный язык регулярен, т.е. существуют языки, не распознаваемые СЦА. В некоторых случаях по описанию языка это свойство может быть установлено. Например, язык, состоящий из всех слов, в которыхчисло нулей равно числу единиц, нерегулярен. Интуитивные соображения состоят в том, что автомат способен “считать” толькодо числа своих состояний, а поскольку число состояний автоматаконечно, то он и не может распознать все слова из этого языка.Но в общем случае задача установления регулярности языка алгоритмически не разрешима.В силу сказанного следует, что надо, по возможности, пользоваться средствами спецификации, обеспечивающими регуляр-26ность языка.
Перечислим некоторые из способов задания регулярных языков.7.1.1. Инициальный конечный автомат с выделенным подмножеством выходных символов I.В автоматном графе всем словам распознаваемого языка итолько словам этого языка соответствуют пути от начала к вершинам или дугам, помеченным символами из множества I. Вбольшинстве случаев можно считать, что множество выходныхсимволов B={0,1}, а множество I={1}.7.1.2. Источник - это ориентированный граф, у котороговыделены начальные вершины и финальные вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
