Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Композиция автоматов
|
|
Пусть заданы автоматы Â 1 и Â 2, имеющие соответственно m 1 и m 2 входов, а также n 1 и n 2 выходов (рис. 7.11).
 |
x 1 y 1 x 1 y 1
... Â 1 ... Â 2
xm 1 yn 1 xm 2 yn 2
Рис. 7.11
Пусть k - такое целое число, что k 
n 1 и k m 2.
Тогда композицией Â 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, Q 1, j1, y1) и Â 2 = (A, A, Q 2, j2, y 2).
Суперпозиция этих автоматов представляет собой автомат
 = (A, A, Q 1 
Q 2, j, y), т.е. множество состояний автомата Â - это множество пар (q i, q j), где q i Î Q 1 и q j Î Q 2.
Пусть начальные состояния автоматов Â 1 и Â 2 - это соответственно q 0 и q l.
Выпишем канонические уравнения для автомата Â:
q 1(t 0) = q 0;
q 2(t 0) = q l;
q 1(t +1) = j1(x (t), q 1(t));
q 2(t +1) = j2(y1(x (t), q 1(t)), q 2(t));
y (t) = y2(y1(x (t), q 1(t)), q 2(t)).
То есть y = y2(y1(x (t), q 1(t)), q 2(t)), где x (t) - это символ на входе Â 1, а q 1(t) и q 2(t) - состояния Â 1 и Â 2 в момент t. Функция перехода j представляет собой пару функций, определяющих первую и вторую компоненты состояния Â в следующий момент времени.