Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Переход от автомата Мили к автомату Мура
|
|
Обычно число внутренних состояний автомата Мура больше или равно числу внутренних состояний автомата Мили. Такое увеличение иллюстрируется рис.13, где показаны фрагменты графов автомата Мили и Мура.
автомат Мили автомат Мура
Рисунок 13. Переход от автомата Мили к автомату Мура
Для лучшего понимания процесса перехода рассмотрим его на примере. Пусть задан автомат Мили совмещенной таблицей переходов (таблица 7), которой соответствует граф, изображенный на рисунке 3.
Таблица 7 – Совмещенная таблица переходов КА Мили
Имеем алфавиты: Z = {Z1, Z2, Z3}; А = {а1, а2, а3, а4}; W = {W1, W2, W3}.
Переход к автомату Мура осуществляется в следующем порядке:
1. Находим множества Вs, определяемые числом различных выходных сигналов на дугах, входящих в данное состояние (см. рис.3).
В1 = {а1W1, а1W2} = {b1, b2}
В2 = {а2W1} = {b3}
ВЗ = {аз W2, азW3} = {b4, b5}
В4 = {а4W3} = {b6}
2. Составляем таблицу переходов автомата Мура на основании таблицы
переходов автомата Мили и состояний Вs (s=1, 2, 3, 4).
Таблица 8 – Т аблица переходов КА Мура
a1 а 2 а 3 a 4
| b i Z i | b1/ W1 | b2/ W2 | b3/ W1 | b4/ W2 | b5/ W3 | b 6/ Wз |
| Z1 | b2 | b2 | b6 | b6 | b6 | -- |
| Z2 | -- - | -- - | b5 | b1 | b1 | -- - |
| Z3 | b3 | b3 | -- | b3 | b3 | b4 |
Для полученного автомата Мура несложно составить граф, понимая, что его выходные сигналы W1, W2, W3 определяются внутренними состояниями b1, …, b6.
Этот граф изображен на рисунке 14.
Рисунок 14. Граф автомата Мура эквивалентного автомату Мили
Пусть автоматы Мили и Мура находятся в начальных состояниях а1 и b2 соответственно. Убедиться в эквивалентности преобразования можно путем подачи на входы исходного автомата Мили и полученного автомата Мура некоторой последовательности букв входного алфавита, например такой:
Z= { Z1, Z1, Z3, Z2, Z1... }
Выходная последовательность обоих автоматов будет следующей:
W = { W2, W2, W1, Wз, Wз,... }.
Значит, абстрактные автоматы Мили и Мура эквивалентны. При этом, выходной алфавит автомата Мура может отличаться от выходного алфавита исходного автомата Мили, поскольку количества внутренних состояний автоматов различно. На этапе структурного синтеза это приводит к тому, что кодировка выходных сигналов автоматов также может отличаться.
|
|