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

...

...

...

 ₁ ...

Рис. 7.12

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

Для простоты будем считать, что множества символов, появляющихся на любых входах и выходах автоматов всегда являются символами одного и того же алфавита.

Упражнение. Определить число выходов композиции автоматов Â ₁ и Â ₂в указанных ранее условиях.

Если автоматы Â ₁ и Â ₂ имеют по одному входу и одному выходу, то композиция таких автоматов, изображенная на рис. 7.13, называется суперпозицией Â и Â ₂.

 ₁  ₂

Â

Рис. 7.13

Пусть заданы два автомата Â ₁ = (A, A, Q ₁, j₁, y₁) и Â ₂ = (A, A, Q ₂, j₂, y ₂).

Суперпозиция этих автоматов представляет собой автомат

 = (A, A, Q ₁ Q ₂, j, y), т.е. множество состояний автомата  - это множество пар (q _i, q _j), где q _i Î Q ₁ и q _j Î Q ₂.

Пусть начальные состояния автоматов Â ₁ и Â ₂ - это соответственно q ⁰ и q ^l.

Выпишем канонические уравнения для автомата Â:

q ₁(t ₀) = q ⁰;

q ₂(t ₀) = q ^l;

q ₁(t +1) = j₁(x (t), q ₁(t));

q ₂(t +1) = j₂(y₁(x (t), q ₁(t)), q ₂(t));

y (t) = y₂(y₁(x (t), q ₁(t)), q ₂(t)).

То есть y = y₂(y₁(x (t), q ₁(t)), q ₂(t)), где x (t) - это символ на входе Â ₁, а q ₁(t) и q ₂(t) - состояния Â ₁ и Â ₂ в момент t. Функция перехода j представляет собой пару функций, определяющих первую и вторую компоненты состояния Â в следующий момент времени.

Пусть 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.

Дата добавления: 2015-03-31