1.2. Классификация автоматов

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

Определение. Автомат называется автоматом Мура, если его функция выходов не зависит существенно от входного символа, то есть если

Очевидно, что функцию выходов автомата Мура можно рассматривать как функцию только от состояния: . Но так как состояние автомата зависит от входа на предыдущем такте, то выход также будет зависеть от входа на предыдущем такте:

Определение. Автомат называется автоматом Мили, если его функция выходов зависит существенно от входного символа, то есть если

Модели автоматов Мура и Мили не являются принципиально различными, напротив, любая из них может быть сведена к другой. Привести модель Мура к модели Мили просто – достаточно добавить в аргументы функции выходов фиктивную переменную, описывающую вход. Приведение модели Мили к модели Мура осуществляется за счет увеличения числа состояний.

Рассмотрим этот процесс подробно. Пусть – автомат Мили. Определим автомат Мура :

• , т.е. состояниями автомата являются пары , где – состояние, а – выход автомата ;

• , если , ;

• .

Пример. Рассмотрим автомат из предыдущего примера. Легко видеть, что он является автоматом Мили.

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

Определение. Автомат, в котором и называется автоматом состояний, или автоматом без выхода, и обозначается .

Автомат состояний используется как модель устройства, функция выходов которого нас не интересует.

Дальнейшая классификация автоматов может быть проведена путем наложения ограничений на мощности их алфавитов.

Определение. Автомат с одноэлементным входным алфавитом называется автономным и обозначается .

Автономный автомат является математической моделью дискретного устройства, в котором

Если в таком устройстве зафиксировать начальное состояние , то в случае всюду определенных функций и можно однозначно определить единственную выходную последовательность и единственную внутреннюю последовательность . Если , то уже среди значений найдутся повторяющиеся, то есть внутренняя и выходная последовательности окажутся периодическими с периодом, не превосходящим , и, возможно, с некоторым предпериодом. Иначе говоря, полный автономный автомат является математической моделью генератора случайных чисел.

Определение. Автомат с одноэлементным внутренним алфавитом называется комбинационным или автоматом без памяти и обозначается . Последнее название оправдано тем, что величину принято называть объемом памяти автомата. Для автомата без памяти .

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

Определение. Автомат с конечными внутренним и входным алфавитами называется конечным автоматом.

Именно конечные автоматы являются математическими моделями реальных дискретных устройств. Далее мы будем рассматривать только конечные автоматы, поэтому договоримся употреблять термины «автомат» и «конечный автомат» как синонимы.