учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С., страница 6

В приведеьвых выше условппх 3 и 4 вэ оговаркваетсв возможнав дпина входных последовательностей. Боли опа ие ограничена, то говорит о полной эквивалентности автоматов. Бслп же достаточно сравнивать автоматы на поспедовательностнх символов длиной нэ боке» чэм в Ф симвопэв, то говерит о Ф -эхвивапэнтности автоматов. Бптественно, что д эхвквапентность автоматов существенно слабее пэпной эквивалентности, так хах д -эквивалентные автоматы могут уже оказатьсн не эквивалентными по отношению х поспедовательностам длиной в ~ +1 символ. 28 Ввэпэвкэ к»витин эхвивапэктнос'Гк кпи ' ж эквквалэвтно стк автоматов позвопкэт ставить вопрос об оптимнзапкк авто мата иа абстрахтнэм уровне путем выбора из возможных автемвт»в таге автомата, который будэт обкапать оптимальным из некоторому критерию апфавктным преобразовавкем Накбепе» часто ставитси в»прес о минимизапии размеров впутрэпвэгэ апфавита, т.е.

миккмкзапии чиспа внутренних сост»кнкй. Преп»дура опткмкзэкик необходимо трэбуэт наличии некоторых дри»мов эхвквапентвогэ преобразовании автоматов на абстрактном уровне. Обычно этк приемы раздепиютск на двэ группы. В первую из нкх входит приемы, обеспечивающи» эквивалэитвзе пр»образованно автоматов Мили в автоматы Мура к обратно, ио вторую - призмы прэобразований внутри кпассов автоматов Минн к Мура. Познакомимск с и»которыми кз ккх. 3,2. Эквквапэитныэ еоб аз»ванин автоматов Мали в автоматы М а и об атно Прэжд» чем обсуждать прап»дуры взаимного прэобразоваики автоматов Мили и Мура, подавно рассмотреть одно разпичие в выпопвэнии этими автэматамн словарного преобразования.

Это разпичиэ удобно обсудить на некотором примере. Рис. 13. Граф автомата Миди Ркс. 14. Граф автомата Мура Пусть автоматы Мили и Мура заданы своими графамк, представленными соответственно на рис. 13 и 14. Попожим, что начальные состоикки этих автоматов, в которые они уста- 27 5,6) ЯЪ.)  ЕЛ хбб выходное слово пп навливаютсн при первоначальном вхлюченик, будут длн автома" та Мили ы к длн автомата Мура о . Педадцм на вхепы каждого кз этих автоматов одно к те же слово Х Хо Х~, 5х, «~1. Тогда процесс словарного преобразования может быть представлен соответствующими словами внутревнкх состояний и выходных символов, которые скмвец за символом могут быть полу ~екы нз графов рассматриваемых автоматов. Для автомата Милн эти слова будут располежены относительно входного слова .в автоматном времени следующим образом: моменты автоматного времеви — 1 2 $4 6. 6 7 8 входное слове х х я .т х х х олене внутренних состояний - ~, Я ~ У 5 Б й выходное слово % У У У У У У Аналогкчно для автомата Мура; моменты аэтоматкого времени - 1 2 3 4 6 6 7 8 входное слово т х х я -тг х х слово внутренних состояний - Ю, ь" я я 5 8 Г Из сравнения выходных последовательностей видно, что рассматриваемые автоматы в данном конхреткам случае ведут себя одинаково с той, однако, разницей, что выходное слзво автомата Мура сдвинуто нн один тахт относцтельно выходного слова автомата Мили.

Выходной символ автомата Мура в момент времени подачи первого входкого сиывола от него не зависит, как это и следует из определения алфавитного преобразования для автомата Мура см.[(1.8) и (1.7)) . Поэтому данный выходной символ игнорируется. В остальном автоматы ведут себя одинаково. С учетом этого различия,допускаемого прк определецик понятия эхвивалентностк автоматов, рассмотрим правила эквивалентного перехода от автомата Мили х автомату Мура и обратно. 3.2.1. Пе вход от автомата Мили х автомату М а. Рассмотрим фрагмент совмещенной таблицы переходов и выходов для автомата Миди, представленный на ркс. 16. На рисунке для удобства дальнейших рассуждений отмечены моменты.

автоматного времени, для которых фиксируются значения соответствующих адфавитов. Ках уже было похазано выше, в автомате Мура выходной сигнал формируется на тахт позже па сравнению с автоматом Мили. Поэтому выходной сигнал, 28 представленный на рнс. 16 в клетке с координатами х,-®,5~Я, 'в автомате Мура будет уже однозначно определяться будущим внутренииы состоянием, т.е. х "(й ). Таккм образом, поведение автомата Мура, получаемого из заданного автомата Мили, будет характеризоваться парами уй(Е +1), У.(Е), непосредственно содержащимися в клетках исходной таблицы для автомата Мили.

Поскольку в такой таблиде одним и тем же внутренним состояниям Яй (6 +1) могут в различных клетках соответствовать различные выходные сигналы, то одному и тому же внутреннему состоянию автомата Мила могут соответствовать несколько внутренних состояний автомата Мура, каждое из которых определяется парой Яй( 6 +1), Уу( ~ ).

Отсюда следует правило перехода от автомата Мили к автомату Мура. Рис. 16. К преобразованию автомата Мили в автомат Мура Исходный автомат Милн представляетсн совмещенной таблицей переходов и въ1ходов. Из атой таблицы выписываетсн список встречавшихся в ее клетках пар 51, У; . Каждой паре ставится в соответствие символ внутреннего состояния автомата Мура у . Вся их совокупность образует алфавит внутренких состояний автомата Мура.

После этого составляется таблица переходов автомата Мура с соответствующим числом строк (их стсльхо же, сколько и у исходного автомата Милн) и. столбцов (число их равно числу символов алфавита внутренних состояний, т.е. числу пар та, У~ ). В клетках столбца, соответствующего состоянию У1, т.е, паре Яа, У . проставляются те переходы 84, которые ранее стояли в клетках столбпа У~ таблкцы автомата Мили в виде самих лар Гй, У.. В 29 Табпкца 6 Табпица 3 в еппик состояний абст хтных автоматов строке выходных сигпалрв для каждого я„записываетея см над, содержащийся в самой парэ 8~, ~..

Рассмотрим пример преобразованкп автомата Мила, представленного графом на рис. 13. Совмещекная таблица дпя тахого автомата прнводатсн ниже (табл. 6). Из приведенной таби 6 выписываются все пары 8,~, ~ и каждой кз них дается обозначение в вкде симвопа внутренних состояний автомата Мура следующим образом: После этого строится т .. автомата Мура. Нетрудно убедиться в том, что подученная табл. 9 описывает автомат, ранее представценный графом на рис. 14. Этоозначает, что рассмотренные ранее автоматы еквивапентиы друг другу.

Обнаруженное выше одинаковое преобразование заданного входного слова этими автоматами оказывается ке спучайным. 3,2.2. Пе еход от автомата М а к автема Мини. Лип осушествпения обратного перехода от автомата Мура к авто- мату Миди удобно воспользоваться представлепкем автомата Мура с помощью графа. Сущность преобразовании заключает- ся в том, что выходные сигналы, записываемые дпи автомата Мура охопо вершин графа, относятся ко всем путям, идущим в эту вершину.

Тем самым одповременко производится изма- ненке момента автоматного времени, к которому откосктся сам выходной сигнал, на один такт вперед. В качестве приме- ра такого преобразовании может быть рассмотрен переход от автомата Мура, заданного графом на ркс. 14. Пепучаемый граф теперь. уже автомата Мики приводится па рис. 16.

Заме тим, что этот граф отппчается от графа автематк Мили па рис. 13, хоти по смыслу выполненных преобразований этэ 30 должны быть графы эквквапептных автоматов. Однако во втором кз щи (граф этого автомата па рпс. 16) чнспо внутренких состояний больше. Уже этот пример говорит о пеобхолнмостк рассмотрения методов минимизации чирка внутренних состояний абстрактных автоматов. Эти метеды обсуждаются виже. Сущность метода минимизации числа внутренних состояний некоторого исходного автомата заключается в разбиении Рпс 16 Г ф М— й - 1 - ~ пп;попучейно ~нз авэо-и секающнеся классы эквивалент- мата Мура, заданного граных состояний с заменой ~ да- фом на рис.14 нее каждого кпасса эхвпв(пзнтиости одним состоянием.

Получающийся в резупьтате минимальный автомат имеет столько же состояний, иа сколько классов эхеквапенткости разбивается все множество внутреннкх состояний заданного автомата. Эхвивапентными называются такие два состоянии автомата, замена которых одно иа другое не изменяет результатов словарвзго преобразования на всем множестве допустимых входных слов. Можно говорить как о припой эквивалентности внутренних состояний (дпя входных снов неограниченной дпины), тах и о д -эквивалентности состояний (дпя слов ~)инной в Ф символов). В дапьнейшем хпассы эквнвапептных к Й-эквивапентных внутренних состояний будут соответственно обозначаться как Ы к Э~ Процедура минимизации числа внутренних состояний абстрактного автомата состоит из следующих шагов: 1.

Находятся последовательные разбиения Эг, ~~, ..., Жй алфавита внутренних состояний на классы одно,- двух-, ..., й - эхвнвапентных состояний, до тех пор, пока на хаком-то к+1 м шаге не окажется, что Х4. =Уй. Очевидно, чтэ при достижении этого тождества можно утверждать, что ~~~= 9, т.е. что Й эквивалентные состояния являются полностью эквивалентными. Нетрудно увядать, что число шагов этой про- 31 цедуры ле может превысить значения 1 -1, где ~ - размеры алфавита внутренних состояиий автомата. 2.

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

10). Таблица 10 таблице имеют одинаковые столбпы. Тогда по табл 11 для э класса Уа полУчаем: йг =1п,, Х, Я, 4„» ) 5, =15,,5„» Таблица 11 Таблица 12 Класс Я выделяется из табл. 1О путем объединении тех внутренних состояний, которые характеризуются одинаковой реакди .й на слова длиной в один символ. Заметим, что в пенятие реакпии входит только выходной сигнал, поскольку ос новным назначением автомата являетсн осуществление словарного преобразования. Для класса У~ выполнюотсн:% = с~'237 гс4т3~5ююк3~21,5~4ткэу~шяптф Строим таблицу Й' (табл. 11), получая ее иэ совмещенной таблицы заменой символов исходного алфавита внутренних состояний на классы 1-эквнвалентности.