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

Функционирование или поведение автомата при заданных множествах ( ) и начальном внутреннем состоянии x₀ полностью детерминировано, и определяется функциями переходов и выходов -

Функция переходов устанавливает зависимость внутреннего состояния автомата в следующий момент времени от состояния входа и внутреннего состояния в настоящий момент времени.

Функция выходов устанавливает зависимость состояния выхода автомата от состояния входа и внутреннего состояния автомата.

Различный характер этих зависимостей для различных автоматов позволяет выделить отдельные типы автоматов в классе синхронных конечных детерминированных автоматов.

Основными являются две модели: Мили и Мура.

Автомат Мили описывается следующими формулами:

1. внутреннее состояние автомата в следующий момент времени зависит от внутреннего состояния автомата в настоящий момент времени и входного сигнала в настоящий момент времени.

2. выходной сигнал автомата в настоящий момент времени зависит от входного сигнала в настоящий момент времени и внутреннего состояния автомата в настоящий момент времени.

Понятие состояния автомата в момент времени t определяется внутренним состоянием автомата и состоянием входа автомата в тот же момент времени.

Автоматы, для которых функции переходов и функции выходов определены на всех парах , называются полностью определенными или полными автоматами. Соответственно, автоматы, для которых функции переходов или функции выходов определены не на всех парах , называются недоопределенными (не полностью определенными) автоматами. Состояние М(t) автомата недоопределенного на соответствующей паре , называется неиспользованным состоянием автомата. Если на каком-либо определенном состоянии автомата не определена только функция выходов, то говорят, что ему соответствует безразличное состояние выхода.

Автомат Мура

Для автомата Мура функции переходов и выходов выглядят следующим образом:

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

Для асинхронного автомата.

Поведение определяется следующим уравнением:

В асинхронном автомате изменение состояния входа вызывает переход в следующее внутреннее состояние, т.е. внутреннее состояние автомата зависит от состояния входа в этот же момент времени, соответственно состояние выхода автомата зависит от состояния его входа.