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

Понятие автомата. Автоматы Мили и Мура, их описание с помощью графов состояний. Построение автомата по блок-схеме алгоритма.

Теория автоматов представляет собой раздел дискретной математики, изучающий модели, преобразователи дискретной информации. Такими преобразователями являются как реальные устройства: компьютеры, живые организмы; так и воображаемые устройства: аксиоматические теории, математические машины.

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

Для описания автомата используют так называемую «шестёрку»: , где:

множество – множество состояний;

множество – множество входных символов;

множество – множество выходных символов;

функция – функция переходов;

функция – функция выходов;

– начальное состояние автомата.

Рисунок 1 – Абстрактный автомат

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

В зависимости от способа определения выходного сигнала в синхронных автоматах различают:

1. Автомат первого рода, который называют автоматом Мили:

Автомат Мили задан системой канонических уравнений:

,

.

Рисунок 2 – Функциональная схема автомата Мили

2. Автомат второго рода, который называют автоматом Мура:

,

,

.

Рисунок 3 – Функциональная схема автомата Мура

Для задания конечного автомата требуется описать все элементы множества . Наиболее часто используемыми формами описания элементов множества являются:

1. Табличный способ;

2. Графический способ;

3. Матричный способ.

Табличная форма автомата Мили иллюстрируется в таблице:

Автомат называется частично заданным, если он определен не для всех пар переходов . Для такого автомата на месте отсутствующего перехода ставится прочерк, как в таблице переходов, так и в таблице выходов.

Графовая форма автомата: представляется графом, в котором:

- множество изображено вершинами графа;

- функция задана дугами графа, причем две вершины графа и соединяются дугой, если в автомате существует переход из в ;

- множество изображено метками дуг: ставится на дуге из вершины в вершину , если в автомате существует переход из в под действием выходного сигнала ;

- функция задана метками дуг (автомат Мили) или метками вершин (автомат Мура).

Для автомата Мили дуга из вершины в вершину помечается выходным сигналом , если в автомате существует переход из в и при этом вырабатывается выходной сигнал .

Для автомата Мура выходным сигналом помечается вершина, определяющая .

Рисунок 4 – Автомат Мили

Рисунок 5 –Автомата Мура