Методы задания конечных автоматов

Наиболее распространены табличный способ задания конечного автомата и представление автомата с помощью ориентированного связанного графа.

Табличное задание автомата Мили

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

Пример:

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

Табличное задание автомата Мура

Две верхние строки задают функцию выходов 2-го рода, а вторая строка и оставшаяся часть таблицы – функцию переходов.

П ример:

Табличное задание С - автомата

В задании на контрольную работу автомат задан двумя таблицами: таблицей переходов и таблицей выходов.

При синтезе конечных автоматов решается задача абстрактного синтеза конечного автомата, а затем задача структурного синтеза автомата. Целью абстрактного синтеза является получение математической модели автомата по техническому заданию и упрощение этой модели. Математическая модель может быть представлена графом автомата, либо таблицей переходов – выходов.

Пример. Синтезировать управляемый генератор периодической последовательности прямоугольных импульсов. Если управляющее входное напряжение равно нулю, то на выходе генератора – ноль. Если управляющее входное напряжение равно единице, то на выходе генератора формируется периодическая последовательность прямоугольных импульсов. Период имеет вид 11010.

Проведем абстрактный синтез этого автомата. Возьмем модель Мили. Для задания конечного автомата нам необходимо определить множества входных сигналов, выходных сигналов, множество состояний, в котором необходимо указать начальное состояние, а также определить функцию переходов и функцию выходов первого рода. Множество входных сигналов состоит из двух элементов, и . Множество выходных сигналов также состоит из двух элементов и . Из этих сигналов можно скомпоновать любую последовательность прямоугольных импульсов. Комбинация выходных сигналов образует необходимый нам период 11010.

Множество внутренних состояний содержит начальное состояние , в котором автомат находится в моменты времени, когда периодическая последовательность не формируется, а также состояния при переходе к которым формируются части периода. Данный конечный автомат можно представить в виде ориентированного графа, в котором состояниям автомата соответствуют вершины графа. Для задания функции переходов и функции выходов первого рода для каждого состояния направленной дугой показывается, в какое состояние переключится автомат в следующий момент времени, входной сигнал, вызывающий это переключение приписывают к началу дуги, а выходной сигнал – к концу дуги.

Д ля структурного синтеза автомата удобнее пользоваться таблицей переходов – выходов, которую легко получить по графу автомата: