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

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

автомат Мили автомат Мура

Рисунок 13. Переход от автомата Мили к автомату Мура

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

Таблица 7 – Совмещенная таблица переходов КА Мили

Имеем алфавиты: Z = {Z₁, Z₂, Z₃}; А = {а₁, а₂, а₃, а₄}; W = {W₁, W₂, W₃}.

Переход к автомату Мура осуществляется в следующем порядке:

1. Находим множества В_s, определяемые числом различных выход­ных сигналов на дугах, входящих в данное состояние (см. рис.3).

В1 = {а₁W₁, а₁W₂} = {b₁, b₂}

В2 = {а₂W₁} = {b₃}

ВЗ = {а_з W₂, а_зW₃} = {b₄, b₅}

В4 = {а₄W₃} = {b₆}

2. Составляем таблицу переходов автомата Мура на основании таблицы

переходов автомата Мили и состояний В_s (s=1, 2, 3, 4).

Таблица 8 – Т аблица переходов КА Мура

a₁ а ₂ а ₃ a ₄

Для полученного автомата Мура несложно составить граф, пони­мая, что его выходные сигналы W₁, W₂, W₃ определяются внутренними состояниями b₁, …, b₆.

Этот граф изображен на рисунке 14.

Рисунок 14. Граф автомата Мура эквивалентного автомату Мили

Пусть автоматы Мили и Мура находятся в начальных состояниях а₁ и b₂ соответственно. Убедиться в эквивалентности преобразования можно путем подачи на входы исходного автомата Мили и полученного автомата Мура некоторой последовательности букв входного алфавита, например такой:

Z= { Z₁, Z₁, Z₃, Z₂, Z₁... }

Выходная последовательность обоих автоматов будет следующей:

W = { W₂, W₂, W₁, Wз, Wз,... }.

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