Задание абстрактных цифровых автоматов

Абстрактный автомат - это модель преобразователя (устройства), которая характеризуется алфавитом входа, алфавитом выхода, алфавитом состояний, функцией перехода и функцией выхода. Взаимосвязь всех параметров автомата описывается выражением

A=< X, Y, S, d, l >, (1.1)

 

где X – входной алфавит автомата, определяющий множество входных сигналов {x₁, x₂, …, x_r};

Y – выходной алфавит автомата, определяющий множество выходных сигналов {y₁, y₂, …, y_p};

S – алфавит состояний автомата, определяющий множество состояний в которых находится или в которые переходит автомат {s₁, s₂, …, s_t};

d – функция переходов автомата, определяющая переход автомата из одного состояния в другое в зависимости от входного сигнала (SxX® S);

l – функция выходов автомата, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала, (SxX® Y).

Семантика: автомат функционирует в дискретном времени. В любой момент времени t_i он находится в некотором состоянии s_i из множества S, и на его вход поступает входной сигнал x_i из множества X. В зависимости от состояния и входного сигнала в следующий момент t_i+1 автомат переходит в новое состояние s_j, определяемое функцией перехода,
s_j =d(s_i, x_i), и на его выходе формируется выходной сигнал y_j=l(s_i, x_i).

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

 

s(t)= d (s(t-1), x (t)), (1.2)

y (t)= l (s(t-1), x (t)).

 

Как видно, закон функционирования представляет собой совокупность двух функций: функции перехода d и функции выхода l.

В формулах используются обозначения:

t - данное автоматное время;

t-1 - предыдущее автоматное время;

d - функция перехода цифрового автомата, формирующая данное состояния s;

l - функция выхода цифрового автомата, формирующая данный выходной сигнал y;

х - входной сигнал.

Данное состояние s(t) зависит от предыдущего состояния s(t-1) и входного сигнала х в данный момент времени. Выходной сигнал y (t) в данный момент времени так же определяется предыдущим состоянием автомата s(t-1) и входным сигналом х в данный момент времени.

Для описания (задания) цифрового автомата используются разнообразные средства, называемые языками [1]. Для описания поведения цифровых автоматов используются таблицы и матрицы переходов и выходов, совмещенные таблицы переходов и выходов, а также графы переходов.

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

Таблица переходов представляет собой совокупность строк и столбцов, причем, строки соответствуют входным сигналам (ВС), а столбцы - предыдущим состояниям (ПС) цифрового автомата. Для таблицы переходов (табл. 1) на пересечениях фиксируются состояния, в которые перейдет автомат при поступлении входного сигнала.

Таблица 1

ПС ВС	s1	s2	s3	s4
x1	s3	s2	s1	s1
x2	s2	s4	s3	s2

 

 

Семантика: если автомат находится в состоянии s₁ и на его вход поступает сигнал x₁, то он перейдет в состояние s₃. При поступлении на вход автомата входного сигнала x₂ он перейдет из состояния s₁ в состояние s₂. Таким образом, таблица переходов описывает переход цифрового автомата из одного состояния в другое при поступлении соответствующего входного сигнала.

Таблица выходов представляет собой совокупность строк и столбцов, причем, строки соответствуют входным сигналам (ВС), а столбцы - предыдущим состояниям (ПС) цифрового автомата. Для таблицы выходов на пересечениях столбцов с предыдущими состояниями цифрового автомата и строк с поступающими входными сигналами фиксируются выходные сигналы цифрового автомата.

 

Таблица 2

ПС ВС	s1	s2	s3	s4
x1	у 3	y 2	y 1	y 1
x2	y 2	y 4	y 3	y 2

 

Семантика: если автомат находится в состоянии s₁ и на его вход поступает сигнал x₁, то на выходе будет формироваться сигнал у ₃. При поступлении на вход автомата входного сигнала x₂ на выходе формируется сигнал у ₃. Таким образом, таблица выходов описывает состояние выхода при переходе автомата из одного состояния в другое при поступлении соответствующего входного сигнала.

По данным таблиц переходов и выходов можно составить совмещенную таблицу переходов и выходов (табл.3), в которой на пересечениях в виде дроби фиксируются состояния и выходные сигналы (s_i / y _i) цифрового автомата.

Таблица 3

ПС ВС	s1	s2	s3	s4
x1	s3 / у 3	s2 / y 2	s1 / y 1	s1 / y 1
x2	s2 / y 2	s4 / y 4	s3 / y 3	s2 / y 2

 

 

Вышеприведенное описание соответствует полностью определенному автомату. Однако при проектировании цифровых автоматов не всегда предоставляется возможность установить явную взаимосвязь между состояниями автомата и состоянием выхода автомата при поступлении входного сигнала. Такие автоматы называются частичными или не полностью определенными.

Частичным (не полностью определенным) автоматом называют автомат, у которого функция перехода dи/или функция выхода lопределены не полностью.

В отдельных ячейках таблиц переходов и выходов не определены состояния в которые может перейти автомат {d (s_i, x_i) =>? } или значение выходного сигнала { l (s_i, x_i) =>? }. При этом следует рассматривать входные сигналы x_i, принадлежащие входному алфавиту X (x_i Î X), как допустимыми так и недопустимыми.

Сигнал x_i допустим в состоянии s_i, если для него возможно определить или поставить в соответствие соответствующее ему состояние или выходной сигнал цифрового автомата. В противном случае входной сигнал считается недопустимым в состоянии s_i.

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

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

Таблица 4

d	s1	s2	s3	s4	s5
x1	s2	s3	s3	--	--
x 2	--	s5	s4	s1	--
x 3	s3	s2	--	s2	s1
x 4	s2	--	s5	--	--

 

Таблица выходов и совмещенная таблица состояний и выходов представлены таблицами 5 и 6 соответственно.

Таблица 5

l	s1	s2	s3	s4	s5
x1	y1	y1	y1	--	--
x 2	y2	y2	y2	y2	--
x 3	--	y1	--	--	y2
x 4	y1	--	y1	--	--

 

 

Таблица 6

d/l	s1	s2	s3	s4	s5
x1	s2 / y1	s3 / y1	s3 / y1	-- / --	-- / --
x 2	-- / y2	s5 / y2	s4 / y2	s1 / y2	-- / --
x 3	s3 / --	s2 / y1	-- / --	s2 / --	s1 / y2
x 4	s2 / y1	-- / --	s5 / y1	-- / --	-- / --

 

При курсовом проектировании цифровой автомат задан совмещенной таблицей переходов и выходов. Для проведения синтеза частичного цифрового автомата по исходной таблице необходимо получить отдельно таблицу переходов и таблицу выходов.

Следующим этапом синтеза цифрового автомата является минимизация его состояний.