Конечным детерминированным автоматом (к.д.а.) Мили называется система 
, где 
, 
, 
– конечные множества (алфавиты), а 
– функции, определенные на этих множествах. Множества X, Y называются соответственно алфавитом состояний, входным и выходным алфавитом, d – функцией переходов, l – функцией выходов. Если, кроме того, в автомате A выделено одно состояние, называемое начальным (обычно будет считаться, что это 
), то автомат называется инициальным. К.д.а. А называется автоматом Мура, если его функция выходов зависит только от состояний, т. е. 
Функцию выходов автоматов Мура считают одноаргументной функцией (
) и называют функцией отметок.
Будучи определенными на конечных множествах функции d и l могут быть заданы с помощью таблицы, которая называется таблицей переходов-выходов (рис. 2.1).
 |
x1 | . . . | xj | . . . | xk |
| s0 s1 |
|||||
| si |  |
||||
 |
В верхнем треугольнике каждой клеточки таблицы записывается значение 
функции переходов, в нижнем – значение 
функции выходов.
Поскольку для автомата Мура значение функции выходов определяется только состоянием, то для каждой строки значение функции выходов (в нижнем треугольнике) одно и то же, поэтому это значение часто выносится в отдельный столбец (рис. 2.2).
|
x1 | . . . | xj | . . . | xk | ||
| s0 s1 |
l (s0 ) | ||||||
| si | d (si,xj ) | l (si ) | |||||
|
l (sr-1 ) |
Другой распространенный способ задания автомата – с помощью диаграммы Мура, фигуры на плоскости (графа), состоящей из вершин, изображаемых точками, и дуг, изображаемых отрезком прямой со стрелкой. Вершины взаимно однозначно соответствуют состояниям автомата, а дуги – входным символам. Из каждой вершины исходит к дуг (к – число символов входного алфавита). Из вершины 
проводится дуга в вершину 
в том и только в том случае, когда 
для некоторого 
. Эта дуга помечается парой 
(рис.2.3).
Начальное состояние в инициальном автомате помечается символом *.
В автомате Мура значение функции выходов (отметка) ставится при вершине, а дуги помечаются только 
(рис. 2.4).
Конечный детерминированный автомат может служить математической моделью технического устройства с конечной памятью, функционирующего в дискретном времени 
Сигналы, поступающие на вход устройства, кодируются буквами входного алфавита X, на выходе сигналы обозначаются буквами выходного алфавита Y. Устройству, имеющему n входов, отвечает автомат со структурным входным алфавитом 
. Состояние автомата характеризует вариант распределения памяти дискретного устройства.
Работа к.д.а. как абстрактного (воображаемого) устройства может быть описана следующим образом.
В каждый момент t дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала x(t) из множества X выдает выходной сигнал y(t) из множества Y согласно функции выходов l, а затем меняет свое состояние на s(t+1) согласно функции переходов d. В момент t=1 автомат находится в некотором начальном состоянии 
. Таким образом, работа автомата может быть описана системой равенств:
для автомата Мили
или
для автомата Мура.
Указанные системы равенств называются каноническими уравнениями. Описывая некоторый дискретный процесс преобразования информации, модель к.д.а. может быть использована для построения функциональной схемы устройства, осуществляющего этот процесс.
Рассмотрим процедуру построения схемы устройства, содержащую этапы:
1) построение к.д.а. на основе какого-либо описания дискретного процесса;
2) минимизация автомата;
3) построение канонической таблицы и канонических уравнений;
4) минимизация канонических уравнений;
5) построение схемы устройства.
В примерах построения к.д.а. преобразование информации задается формулами.
