Операция обратной связи

Пусть A = { a ₀,..., a _n } - некоторый алфавит. Определим специальный автомат Z = (A, A, A, j, y) следующими каноническими уравнениями:

q (t ₀) = a ₀;

q (t +1) = x (t);

y (t) = q (t).

Нетрудно видеть, что на первом шаге работы автомат Z находится в состоянии, обозначенном первым символом алфавита A,и подает на выход именно этот символ. В каждый последующий момент автомат Z подает на выход символ, который равен символу на входе этого автомата в предыдущий момент времени.

Автомат Z называется автоматом задержки на один такт или один шаг.

Пусть Â = (A^m, Aⁿ, Q, j, y) - произвольный конечный автомат, имеющий m входов и n выходов. При этом m, n ³ 2.

ОПРЕДЕЛЕНИЕ

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

В результате операции обратной связи образуется новый автомат с m - 1 входами и n - 1 выходами.

Пример. На рис. 7.14 изображен конечный автомат Á, который получается из автомата Â, имеющего по два входа и выхода, применением обратной связи:

x (t) y (t)

Â

Z

Á

Рис. 7.14

Состояниями Á являются пары (q _i, q _j), где q _i - состояние Â, а q _j - состояние автомата задержки Z.

Пусть q ⁰- начальное состояние автомата Á.

Тогда функционирование автомата Â для заданных начальных состояний q ⁰ и a ₀ представляется следующими каноническими уравнениями:

q1(t0)	=	q^0;
q2(t0)	=	a0;
q1(t+1)	=	j((x (t), q2(t)), q1(t));
q2(t+1)	=	y2((x (t), q2(t)), q1(t));
y(t)	=	y1((x (t), q2(t)), q1(t)).

Здесь q ₁(t) и q ₂(t) - состояния Â и Z в момент t, а y₁ и y₂ - функции, определяющие символы на первом и втором выходах автомата Â соответственно.

Входные символы для автомата Â представляют собой пары символов (x ₁(t), x ₂(t)).

Упражнение. Записать канонические уравнения для автомата задержки на два шага, изображенного на рис. 7.15.

Z Z

Рис. 7.15

ОПРЕДЕЛЕНИЕ

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

Дата добавления: 2015-11-30