Определение, способы представления конечного автомата

Конечный автомат содержит управляющее устройство, входной и выходной каналы. Для управляющего устройства выделено начальное состояние q₀. Работа автомата осуществляется в дискретные такты времени t= 1, 2, 3, …. На входной канал автомата последовательно поступают символы x₁, x₂, …, при этом управляющее устройство изменяет свое состояние, а на выходе появляются выходные символы y₁, y_2, …. Работа автомата определяется системой команд, каждая из которых имеет вид q_ix_r ® q_jy_s, где q_i, q_j – внутренние состояния автомата, x_r – входной символ, y_s – выходной символ. Обычно требуют, чтобы выполнялось условие однозначности, т.е. не может быть двух команд с одинаковыми левыми и различными правыми частями. Такой автомат называется детерминированным. Выходной символ, вырабатываемый автоматом, зависит не только от входного символа на текущем такте времени, но и от внутреннего состояния. В свою очередь, внутреннее состояние автомата зависит от входных символов, поступивших в предыдущие такты времени. В этом смысле автомат обладает памятью.

Дадим формальное определение конечного автомата. Конечный автомат M=(Q, X, Y, d, l), где Q={q₀, q₁, …, q_k} – конечное множество внутренних состояний автомата, X={x₁, x₂, …, x_n} – множество входных символов (входной алфавит), Y={y₁, y₂, …, y_m} – множество выходных символов (выходной алфавит), d(q,x) : Q´X ® Q – функция переходов автомата из одного состояния в другое, l(q,x) : Q´X ® Y – функция выходов. Состояние автомата соответствует памяти о прошлом, позволяя устранить время как явную переменную. Автомат обычно задают таблицей переходов, в заголовках строк которой стоят все возможные состояния автомата, в заголовках столбцов – все символы входного алфавита, а на пересечениях строк и столбцов – следующее состояние автомата и выходной символ.

Пример 5.1. Рассмотрим таблицу переходов некоторого автомата с входным алфавитом X={a, b}, выходным алфавитом – Y={b, c}, множеством состояний Q={q₁, q₂, q₃}.

Пусть на вход автомата поступает последовательность символов a, a, b, a. Рассмотрим работу автомата: .
На выходе автомата получится последовательность c, b, c, b.

Автомат можно также наглядно задать с помощью ориентированного мультиграфа, называемого графом переходов состояний. Вершины этого графа соответствуют состояниям, дуга ведет из вершины q_i в вершину q_j, если d(q_i, x_r)=q_j и l(q_i, x_r)=y_s, причем каждой дуге приписана пара x_r, y_s. Кратные дуги из вершины q_i в вершину q_j заменяются одной дугой, которой приписаны несколько пар входной – выходной символы.

Пример 5.2. Построим граф переходов состояний для примера 5.1.

 

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

1) для любого входного символа x_r имеется дуга, выходящая из q_i и помеченная x_r (условие полноты);

2) любой символ x_r встречается только на одной дуге, выходящей из q_i (условие детерминированности).

Пример 5.3. Построим граф переходов для двоичного сумматора, который по данным двум n-разрядным двоичным числам вычисляет их сумму. Входные данные начинаются с битов с наименьшими значениями, пары битов читаются справа налево.

Двойная окружность на вершинах означает, что эти состояния – заключительные. Пусть суммируются числа 011010 и 001100. Тогда на вход автомата поступает последовательность 00, 10, 01, 11, 10, 00. Рассмотрим работу автомата:

.

На выходе автомата получим последовательность 0, 1, 1, 0, 0, 1.