3Etap (Лекция), страница 4

Два абстрактных автомата с одинаковым входным Xи выходным Y алфавитами называются эквивалентными, если онииндуцируют одно и то же отображение множества входных слово множествовыходных слов.Важным вопросом является установление взаимосвязи междумоделями автоматов Мили и Мура.ТеоремаГлушкова:ДлялюбогоавтоматаМилисуществуетэквивалентный ему автомат Мура с числом состояний Q≤m*n+1 где m- числовходных букв, n- число состояний в автомате Мили.Автоматное отображение автомата Мура сдвинутого (запаздывает) на 1такт по отношению к автоматному отображению автомата Мили.Автомат Мили – это модель более общая, позволяющая записыватьопределённое количество выходных сигналов с меньшим числом состояний.Автомат Мура имеет более простую граф-схему переходов и проще втехнической реализации.Существуют приёмы, позволяющие перейти от представленияавтомата Мили к автомату Мура, а также обратно.1) Переход Мили – МураПусть задан автомат Мили графом:x2/y1x1/y2x1/y2S0S1x2/y1и таблицами переходов и выходов:S0 S1S0 S1х1 S1 S1х1 y2 y2х2 S0 S0х2 y1y1Рассмотрим работу автомата Мили на 6 тактах.t = 1 2 3 4 5 6x = х1 х1 х1 x2 x2 х1y = y2 y2 y2 y1 y1 y2Тривиальный переход от автомата Мили к автомату Мура возможен вслучае, когда все входные стрелки в состояние Si имеют одну и ту жереакцию.

В рассматриваемом примере это требование выполняется. Вавтомате Мура начальное состояние q0 всегда выделяется, и оно вместе ссостоянием q1 соответствует состоянию S0:S0 => {q0, q1},S1 => {q2}.В результате эквивалентный автомат Мура выглядит так:х2y1x1y2q2q1x1x2x2x1qo-2) Общий случай перехода от автомата Мили к автомату Мура.Пример : Автомат проводит пересчёт входных импульсов по mod 3, арезультат выдаётся только при отсутствии входного импульса.X = {I, _ },Y = {0, 1, 2, e}S1I/eL /1 _ /1_ /0S0-/2I/eI/I/eS2S = {S0, S1, S2}.Верхняя оценка количества состояний эквивалентного автомата Мураопределяется по теореме Глушкова: Q = 2*3+1 = 7. Рассмотрим по шагампроцедуру преобразования автомата Мили в автомат Мура.а) Строится совмещенная таблица переходов-выходов автомата Мили.И каждая клетка этой таблицы отмечается последовательно состояниями qi.I_S0S1S2S1/eS2/eS0/eq1q3q5S0/0S0/1S0/2q2q4q6б) Установление соответствия состояний Si множеству состояний qj.S0{q2, q4, q5, q6, q0},S1{q1},S2{q3}.3) Построение отмеченной табл.

автомата МураВых.-e0e1e2Сост. q0 q1 q2 q3 q4 q5 q61q1 q3 q1 q5 q1 q1 q1Lq2 q4 q2 q6 q2 q2 q24) Заполнение выходных сигналов таблицы.5) Минимизация состояний (склеивание одинаково обозначенныхстолбцов с одинаковыми выходными буквами).В данном примере не минимизируется граф.Эксперимент с автоматом Мили и Мура на выходное слово /// // /Автомат Мили:S2S3S1S1S2S3S1S2 S0eee0ee2e1Автомат Мура:q0q1q3q5q2q1q3q6q1q4-eee0ee2e1В общем случае|Q| >|S|Переход от автомата Мура к автомату Мили.ТривиальныйS| = |Q|-1, исключается qo.Пример: Т – триггер0110q1q2110qo0/01/1S10/1S21/0.