7.3. Связь между моделями Мили и Мура

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

Пусть задан автомат Мура М = (A, B, Q, , ) и требуется получить эквивалентный ему автомат Мили М^ = (A^, B^, Q^, ^, ^).

Очевидно, А^ = А и В^ = В. Положим Q^ = Q и ^ = , а ^ определим следующим образом. Пусть (a, q)  q и (q)  b, где q, q  Q, a  А и b  В. Это означает, что автомат, будучи в состоянии q, отвечает на входной символ а выходным символом b, который выдается в следующий момент времени, когда автомат окажется в состоянии q. Следовательно, можно считать, что ^(а, q)  b. Автомат Мура и эквивалентный ему автомат Мили представлены в табл. 7.6 и 7.7 соответственно.

Пусть теперь задан автомат Мили М = (A, B, Q, , ) и требуется получить эквивалентный ему автомат Мура М^ = (A^, B^, Q^, ^, ^). Как и в предыдущем случае, имеем А^ = А и В^ = В. Определим Q^ следующим образом. Рассмотрим все такие пары вида (q, b), где q  Q, b  B, что для каждой (q, b) имеется такая пара (a, q), что (a, q)  q и (a, q)  b (a  A, q  Q). Каждой паре (q, b) поставим в соответствие состояние q^  Q^ и определим функции ^ и ^ следующим образом:

^(a, q^)  ^(a, (q, b))  ((a, q), (a, q)); ^(q^)  ^((q, b))  b.

  Таблица 7.6  Таблица 7.7

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

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

         Таблица 7.8 Таблица 7.9