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

Конечный автомат содержит управляющее устройство, входной и выходной каналы. Для управляющего устройства выделено начальное состояние 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 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.

Автомат можно также наглядно задать с помощью ориентированного мультиграфа, называемого графом переходов состояний. Вершины этого графа соответствуют состояниям, дуга ведет из вершины 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 3

q 1

q 2

a,c

a,b

b,c

a,b

b,b

b,c

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

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

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

11,0

q 0

q 1

00,1

01,0

10,0

11,1

01,1

10,1

00,0

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

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

.

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