Способы задания конечного автомата

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

Пример 1. Зададим автомат следующим образом: , , .Функцию определим с помощью таблицы переходов, а функцию – с помощью таблицы выходов.

Таблица 1. Таблица переходов Таблица 2. Таблица выходов

Вход	Состояние

Вход	Состояние

Если известна последовательность сигналов на входе автомата, то таблицами переходов и выходов однозначно определяется выходная последовательность.

2°. Графический способ задания. Используется диаграмма переходов-выходов. Она представляет собой ориентированный мультиграф, в котором каждому внутреннему состоянию автомата соответствует вершина. Переходы автомата из состояния в состояние изображаются стрелками, на каждой из которых пишутся входной символ, вызывающий данный переход, и выходной символ, вырабатываемый автоматом.

| |

| |

|

Рис.1 Диаграмма переходов-выходов

Пример 2. Требуется построить автомат, который работал бы следующим образом: в каждый такт на вход автомата поступают очередные двоичные разряды слагаемых, автомат вырабатывает соответствующий двоичный разряд их суммы. Для двухразрядных слагаемых имеем: , , .

Автомат находится в состоянии 1, если при сложении предыдущих разрядов возникает перенос, и в состоянии 0 – в противном случае. Диаграмма переходов-выходов показана на рис. 2.

1

0

10|1 00|1 11|1

Рис. 2