173
правки
Изменения
→Переход от автомата Мили к автомату Мура
Рассмотрим пример, в котором <tex>Z_{B} = \{z_{1}, z_{2}\} = Z_{А}</tex>, <tex>W_{B} = \{w_{1}, w_{2}\} = W_{A}</tex>, алфавит состояний автомата Мили содержит три элемента.
Для определения алфавита состояний, функций переходов и выходов автомата Мура воспользуемся следующей вспомогательной таблицей.
В данном случае <tex>A_{B} \neq A_{A}</tex>.
При таком переходе (Мили к Мура) каждому состоянию автомата Мили as ставится в соответствие множество всевозможных пар <tex>a_{s} \rightarrow A_{s} = \{( a_{s}, w_{g}) | a_{s} = \delta(a_{m}, z_{f}), w_{g} = \lambda(a_{m}, z_{f})\}</tex>, где <tex>a_{s}</tex> есть функция <tex>\delta</tex> от состояния и входного сигнала, <tex>w_{g}</tex> функция <tex>\lambda</tex> от состояния и входного сигнала.
Пример:
<tex>A_{s} = \{(a_{s}, w_{1}), (a_{s}, w_{2}), (a_{s}, w_{3})\}</tex>.
Для состояния <tex>a_{1} = </tex>
Для состояния <tex>a_{2} = </tex>
Для состояния <tex>a_{3} = </tex>
В качестве начального состояния результирующего автомата может быть выбрано любое состояние Мура, порожденное начальным состоянием автомата Мили, т.е. состояния <tex>b_{1}</tex> или <tex>b_{2}</tex>.
При определении функции переходов результирующего автомата Мура из всех состояний, порожденных одним состоянием автомата Мили, должны быть переходы под воздействием одинаковых входных сигналов.
Поскольку в автомате Мура выходной сигнал зависит только от состояния автомата, то в примере рядом с состояниями проставим соответствующие выходные сигналы.
И так если осуществить следующие преобразования, то получим:
Можно утверждать, что если <tex>S_{1}</tex> эквивалентно <tex>S_{2}</tex>, а <tex>S_{2}</tex> эквивалентно <tex>S_{3}</tex>, то <tex>S_{1}</tex> эквивалентно <tex>S_{3}</tex> (т.е. эквивалентность обладает свойством транзитивности).
Таким образом возникает задача минимизации автоматов, под которой понимается задача нахождения в классе всех эквивалентных автоматов автомата того же типа (Мили или Мура) с минимальным числом состояний.
