Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Переход от автомата Мили к автомату Мура и обратно

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

Рассмотрим переход от автомата Мура к автомату Мили. Пусть задан автомат Мура:

^А ~ А’ Р/4’ Ф/1’ Х,А).

Необходимо построить автомат Мили, эквивалентный автомату Мура:

~ {Xв-* фд, 1|/5,

Р а = Рд5 Л л = Л5.

Функцию |/й определим следующим образом: если в автомате Мура имеются функции Ат, р5) = х5, гА5) = X , то для автомата Мили можно записать следующую функцию выхода: г вт, рЛ.) = Аг

Рассмотрим переход от автомата Мура к автомату Мили с помощью графа (рис. 6.5). Для осуществления перехода от автомата Мура к автомату Мили выходной сигнал X, находящийся в автомате Мура рядом с вершиной, для автомата Мили передается на все дуги, входящие в эту вершину.

Переход от автомата Мура к автомату Мили с помощью графа

Рис. 6.5. Переход от автомата Мура к автомату Мили с помощью графа

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

Из самого способа построения автомата Мили очевидно, что он эквивалентен автомату Мура. Для входной последовательности Ф поведение автоматов 5^ и полностью совпадают. По индукции нетрудно доказать, что любое входное слово конечной длины, поданное на входы автоматов и 3^, установленных в начальное состояние х0, вызовет появление одинаковых выходных слов.

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

Задан автомат Мили 5^. Необходимо построить автомат Мура Я#. Алфавиты должны совпадать:

Для определения множества Хв каждому состоянию е XА поставим соответствующее множество пар вида = ^х5, Х где Хявыходной сигнал, приписанный дуге, входящей вхЛ. (рис. 6.6).

Выходной сигнал

Рис. 6.6. Выходной сигнал

Число элементов в множестве Х5 будет равно числу различных выходных сигналов на дугах автомата Мили 5^, входящих в состояние ха. Число внутренних состояний автомата Мура будет определяться объединением множеств всех Х5:

Хв = их5;

хл => Хв.

Функция переходов фд и функция выходов гв определяются так: если в автомате Мили имеется переход из состояния хт в состояние под воздействием р,

Фя(*,и> Р/) =

и при этом выдается выходной сигнал А, •

Р/> =

то в автомате Мура будет переход из множества состояний Х’т порождаемых внутренним состоянием хт под воздействием входного сигнала р,:

ф*«*;ь Р/) = х;.

Функция выходов автомата Мура определяется следующим образом:

= V

В качестве начального состояния хов можно взять любое состояние из множества, которое порождается начальным состоянием:^.

Таким образом, получается автомат эквивалентный автомату (рис. 6.7).

Изложенные методы взаимных транспозиций моделей Мили и Мура показывают, что при переходе от автомата Мура к автомату Мили число состояний автомата не меняется, а при обратном пере-

р!

*1

Автомат Мили (а) эквивалентен автомату Мура (б)

Рис. 6.7. Автомат Мили (а) эквивалентен автомату Мура (б)

ходе число состояний, как правило, возрастает. Вследствие транзитивности отношения эквивалентности => = ,5^,. Два

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

Вопросы и задания для самопроверки
  • 1. Каковы основные задачи, решаемые в теории автоматов?
  • 2. Из каких компонентов состоит автомат?
  • 3. Что представляет собой память автомата?
  • 4. Каковы основные особенности конечного автомата?
  • 5. В чем разница между синхронными и асинхронными автоматами?
  • 6. Какую зависимость описывает функция переходов?
  • 7. В чем различия между автоматами Мили и Мура?
  • 8. Какие языки используются для задания автомата?
  • 9. Что характеризуют вершины графа автомата?
  • 10. Как меняется число состояний при переходе от автомата Мили к автомату Мура?
 
<<   СОДЕРЖАНИЕ   >>