Автоматы Мили и Мура. Размеченные графы

Рассмотренные ранее автоматы – это классические автоматы Мили. Автомат Мура – это автомат, выходы которого зависят только от текущего состояния:

,

где – алфавит входных сигналов; – алфавит выходных сигналов; , , .

Автомат Мура – частный случай автомата Мили.

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

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

Несколько изменяется представление графа. Обозначение выхода ставится возле каждого узла (рис. 4.5).

Рис. 4.5. Графическое представление автомата Мура

Дата добавления: 2015-06-04