Конечный автомат содержит управляющее устройство, входной и выходной каналы. Для управляющего устройства выделено начальное состояние q0. Работа автомата осуществляется в дискретные такты времени t= 1, 2, 3, …. На входной канал автомата последовательно поступают символы x 1, x 2, …, при этом управляющее устройство изменяет свое состояние, а на выходе появляются выходные символы y 1, y 2, …. Работа автомата определяется системой команд, каждая из которых имеет вид qixr ® qjys, где qi, qj – внутренние состояния автомата, xr – входной символ, ys – выходной символ. Обычно требуют, чтобы выполнялось условие однозначности, т.е. не может быть двух команд с одинаковыми левыми и различными правыми частями. Такой автомат называется детерминированным. Выходной символ, вырабатываемый автоматом, зависит не только от входного символа на текущем такте времени, но и от внутреннего состояния. В свою очередь, внутреннее состояние автомата зависит от входных символов, поступивших в предыдущие такты времени. В этом смысле автомат обладает памятью.
Дадим формальное определение конечного автомата. Конечный автомат M=(Q, X, Y, d, l), где Q={q 0, q 1, …, qk} – конечное множество внутренних состояний автомата, X={x 1, x 2, …, xn} – множество входных символов (входной алфавит), Y={y 1, y 2, …, ym} – множество выходных символов (выходной алфавит), d(q,x): Q´X ® Q – функция переходов автомата из одного состояния в другое, l(q,x): Q´X ® Y – функция выходов. Состояние автомата соответствует памяти о прошлом, позволяя устранить время как явную переменную. Автомат обычно задают таблицей переходов, в заголовках строк которой стоят все возможные состояния автомата, в заголовках столбцов – все символы входного алфавита, а на пересечениях строк и столбцов – следующее состояние автомата и выходной символ.
Пример 5.1. Рассмотрим таблицу переходов некоторого автомата с входным алфавитом X={a, b}, выходным алфавитом – Y={b, c}, множеством состояний Q={q 1, q 2, q 3 }.
|
| a
| b
| | q 1
| q 2, c
| q 3, c
| | q 2
| q 1, b
| q 2, c
| | q 3
| q 2, b
| q 1, b
|
|
Пусть на вход автомата поступает последовательность символов a, a, b, a. Рассмотрим работу автомата: 
.
На выходе автомата получится последовательность c, b, c, b.
Автомат можно также наглядно задать с помощью ориентированного мультиграфа, называемого графом переходов состояний. Вершины этого графа соответствуют состояниям, дуга ведет из вершины qi в вершину qj, если d(qi, xr)=qj и l(qi, xr)=ys, причем каждой дуге приписана пара xr, ys. Кратные дуги из вершины qi в вершину qj заменяются одной дугой, которой приписаны несколько пар входной – выходной символы.
Пример 5.2. Построим граф переходов состояний для примера 5.1.
Не любой ориентированный мультиграф, все дуги которого помечены подобным образом, соответствует некоторому автомату. Для соответствия автомату в каждой вершины
qi должны выполняться следующие два условия:
1) для любого входного символа xr имеется дуга, выходящая из qi и помеченная xr (условие полноты);
2) любой символ xr встречается только на одной дуге, выходящей из qi (условие детерминированности).
Пример 5.3. Построим граф переходов для двоичного сумматора, который по данным двум
n -разрядным двоичным числам вычисляет их сумму. Входные данные начинаются с битов с наименьшими значениями, пары битов читаются справа налево.
Двойная окружность на вершинах означает, что эти состояния – заключительные. Пусть суммируются числа 011010 и 001100. Тогда на вход автомата поступает последовательность 00, 10, 01, 11, 10, 00. Рассмотрим работу автомата:
.
На выходе автомата получим последовательность 0, 1, 1, 0, 0, 1.
