3.6. Абстрактная и структурная теория конечных автоматов

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

Автомат называется комбинационным, если для любого входного символа а и любых состояний q_i и q_j (q_i, a)= (q_j, a), иначе говоря, если выходной символ не зависит от состояния и определяется текущим входным символом. В таком автомате все состояния эквивалентны и, следовательно, минимальный комбинационный автомат имеет одно состояние. Функция переходов в нем вырождена и его поведение однозначно задается функцией выходов с одним аргументов: (a_i)=v_i.

Все автоматы можно подразделить на синхронные и асинхронные. Известны две модели синхронных элементарных автоматов: модель Мура и модель Мили, получившие названия по именам ученых, разработавших соответствующие разделы теории автоматов. Моделью Мура называется автомат, описываемый уравнениями:

q(t) = [x(t-1); q(t-1)]; v(t)=  [q(t)],

где q(t), q(t-1) - состояния автомата в моменты времени t и t-1; x(t-1), v(t) - входной и выходной сигналы автомата в моменты времени t и t-1.

Для модели Мили справедливы соотношения:

q(t) = [x(t-1); q(t-1)];

v(t)=  [x(t); q(t)].

Существует несколько способов представления конечных автоматов, основными из которых является графический, таблично - матричный, аналитический с использованием секвенциальных уравнений. Пусть необходимо синтезировать автомат, разрешающий работу некоторого устройства при наличии единичных сигналов на входах Х₁, Х₂ , причем, для включения устройства необходимо выполнить условие появления сигнала на входе Х₁ раньше, чем на входе Х₂. При графическом способе описания данный автомат можно представить в виде направленного графа (рис. 3.8 и 3.9), вершинами которого являются состояния автомата, а ребрами - комбинации выходных сигналов.

00 v 01 v 10

11

11

00 v 01

11

10

01 v 00

10

Рис. 3.8 - Граф автомата Мура

10/0

Рис.3.9 - Автомат Мили.

Как видно из графа, комбинация (01) вызывает переход автомата из некоторого состояния S₀ в состояние S₁, соответствующее появлению единичного сигнала на выходе У автомат может перейти только из состояния S₁ при условии поступления комбинации входных сигналов Х₁, Х₂ (11). Данный граф соответствует представлению автомата моделью Мура т.к. выходной сигнал (указан в узлах графа) полностью определяется внутренним состоянием автомата и не зависит от комбинации сигналов на входе. При задании автомата моделью Мили его выходной сигнал указывается над каждым ребром графа (см. рис. 3.4), т.к. зависит не только от внутреннего состояния автомата, но и от комбинации сигналов, поступающих на вход автомата в данный момент времени.

Вместо построения графа всю необходимую информацию о работе можно свести в специальные автоматные таблицы: таблицу переходов и таблицу выходов. Представление автомата при помощи таблиц показано в таблицах 3.6 - 3.9.

Таблица 3.6 - Таблица переходов автомата Мура

Состояния	Входные сигналы
		00	01	11	10
g0		g0	g0	g1	g0
g1		g0	g0	g1	g2
g2	g0	g0	g1	g2

Таблица 3.7 - Таблица выходов автомата Мура

Состояние	g0	g1	g2
Выходные сигналы	0	0	1

Таблица 3.8 - Таблица переходов автомата Мили

Состояния	Входные сигналы
		00	01	11	10
g0		g0	g0	g1	g0
g1		g0	g0	g1	g1

Таблица 3.9 - Таблица выходов автомата Мили

Состояния	Выходные сигналы
		00	01	11	10
g0		0	0	0	0
g1		0	0	0	1

На пересечении строк и столбцов автоматных таблиц указываются внутренние состояния, в которые переходит автомат под действием входных сигналов и выходные сигналы, которые он при этом выдает. Обе рассмотренных формы задания автоматов построены для одного и того же примера автоматов Мура и Мили.