7.7. Схемы конечных автоматов
Рассмотрим операции над автоматами, которые позволяют из одних автоматов образовывать другие автоматы. В частности, если задано фиксированное семейство простых автоматов, то из экземпляров автоматов семейства можно строить другие автоматы или даже любые возможные автоматы.
Для этого нам потребуется рассматривать входы и выходы автоматов как конечные системы входов и выходов.
То есть автомат может рассматриваться как устройство, имеющее несколько входов и несколько выходов, которые мы будем обозначать символами переменных x1, . . . , xm и y1, . . . , yn соответственно.
Тогда символами входного алфавита автомата , имеющего m входов, являются наборы длины m, компоненты которых одновременно поступают на входы .
Символы выходного алфавита , имеющего n выходов, это наборы длины n, значения всех компонент которых одновременно появляются на выходах автомата в качестве результата его работы.
К основным операциям над автоматами относятся композиция и обратная связь.
7.7.1. Композиция автоматов
Пусть заданы автоматы 1 и 2, имеющие соответственно m1 и m2 входов, а также n1 и n2 выходов (рис.7.11).
x1 y1 x1 y1
. . . 1 . . . 2
xm1 yn1 xm 2 yn2
Рис. 7.11
Пусть k такое целое число, что k n1 и k m2.
Тогда композицией 1 и 2 называется автомат, который получается из 1 и 2 подсоединением k различных выходов 1 к k различным входам 2.
Например, так как это выполнено для случая, изображенного на рис.7.12.
. . . 2
. . .
1 . . .
. . .
. . .
Рис. 7.12
Понятно, что функционирование полученного устройства является корректным, если символы, появляющиеся на выходах 1 и поступающие на входы 2 принадлежат одному и тому же алфавиту.
Для простоты будем считать, что множества символов, появляющихся на любых входах и выходах автоматов всегда являются символами одного и того же алфавита.
Упражнение. Определить число выходов композиции автоматов 1 и 2 в указанных ранее условиях.
Если автоматы 1 и 2 имеют по одному входу и одному выходу, то композиция таких автоматов, изображенная на рис. 7.13, называется суперпозицией и 2.
1 2
Рис. 7.13
Пусть заданы два автомата 1 = (A, A, Q1, 1, 1) и 2 = (A, A, Q2, 2, 2).
Суперпозиция этих автоматов представляет собой автомат
= (A, A, Q1 Q2, , ), т.е. множество состояний автомата это множество пар (qi, qj), где qi Q1 и qj Q2.
Пусть начальные состояния автоматов 1 и 2 это соответственно q0 и ql.
Выпишем канонические уравнения для автомата :
q1(t0) = q0;
q2(t0) = ql;
q1(t+1) = 1(x(t), q1(t));
q2(t+1) = 2(1(x(t), q1(t)), q2(t));
y(t) = 2(1(x(t), q1(t)), q2(t)).
То есть = 2(1(x(t), q1(t)), q2(t)), где x(t) это символ на входе 1, а q1(t) и q2(t) состояния 1 и 2 в момент t. Функция перехода представляет собой пару функций, определяющих первую и вторую компоненты состояния в следующий момент времени.