Композиция автоматов
К операциям композиции (объединению) относятся известные три соединения: последовательное, параллельное, соединение с обратной связью и соединение в сеть. Располагая совмещенными таблицами переходов, выходов исходных цифровых автоматов А1 и А2, нужно при старте из любого предыдущего состояния определить новое состояние объединенного автомата А и его выходной сигнал соединения.
Последовательное соединение автоматов Последовательное соединение автоматов рассмотрим на примере схемы, представленной на рисунке 2.
Рисунок 2 Последовательная схема соединения
Исходные автоматы - это автоматы А1 и А2, а результирующий – автомат А, которые описываются множествами
А1 = {Х1, Y1, S1, d1, l1}, А2 = {Х2, Y2, S2, d2, l2}, (1.7) А = {Х, Y, S, d, l}.
Из рисунка 2 следует следующее равенство входных и выходных слов (сигналов):
Х1 = Х; Y1 = X2; Y2 = Y,
где Х1 – входной алфавит автомата А1; Х2 – входной алфавит автомата А2; Х – входной алфавит объединенного автомата А; Y1 - выходной алфавит автомата А1; Y2 - выходной алфавит автомата А2; Y - выходной алфавит объединенного автомата А. Алфавитом состояний объединенного автомата S будет произведение алфавитов состояний первого S1 и второго S2 автоматов S = S1 × S2. Тогда для любого состояния объединенного автомата S {(s1i × s2j) Î S, где s1i Î S1 а s2j Î S2} должно выполняться условие:
d((s1i × s2j), х) = (d1(s1i, х 1) × d2(s2j, l1(s1i, х 1), х)), (1.8)
l ((s1i × s2j), х) = l2(s2j, l1(s1i, х 1)), (1.9)
где d1, d2 и d функции перехода первого автомата, второго автомата и объединенного автомата соответственно; l1, l2 и l - функции выхода первого автомата, второго автомата и объединенного автомата соответственно. Докажем справедливость вышеприведенных равенств. Состояние объединенного автомата будет определяться функцией перехода d sк = d((s1к × s2к), х). (1.10)
Состояние автомата А1 определяется функцией перехода d1
s1к = d1(s1i, х 1). (1.11)
Состояние автомата А2 определяется функцией перехода d2
s2к = d1(s2j, х 2). (1.12)
При условии, что х 2 = y1 и с учетом равенства y1 = l1(s1i, х 1) выражение (1.11) примет вид
……… s2к = d1(s2j, l1(s1i, х 1)). (1.13)
Подставив выражения (1.10), (1.11) и (1.13) в уравнение (1.8) получим выражение функции переходов объединенного автомата. Аналогично проведем доказательства для функции выхода объединенного автомата. yк = l ((s1i × s2j), х). y1к = l1(s1i, х 1), y2к = l2(s2j, х 2). При условии, что х 2 = y1 получим y2к = l2(s2j, l1(s1i, х 1)). Исходя из схемы последовательного соединения видно, что yк = y2к, отсюда l ((s1i × s2j), х) = l2(s2j, l1(s1i, х 1)), что соответствует выражению (1.8) функции выхода объединенного автомата. Изложенные теоретические положения проиллюстрируем на примере автоматов Мили. Совмещенные таблицы переходов и выходов для А1, А2 представлены в таблицах13 и 14 соответственно. Таблица 13 Таблица 14
Пусть для последовательного соединения заданы предыдущие состояния объединенного автомата s1 (s11, s21) при входном сигнале х 12. Алгоритм последовательного соединения автоматов можно сформулировать следующим образом: - начать; - перебирать все состояния S; - по состоянию S определить пару состояний автоматов А1 и А2 (sa1, s a2); - по входному сигналу x определить новое состояние автомата А1 sa1, и его выходной сигнал y a1; - по выходному сигналу автомата А1 y a1, который является входным сигналом автомата А2, определить новое состояние автомата А2 s a2, и выходной сигнал автомата А2 y a2; - по состояниям автоматов А1 и А2 (sa1, s a2) определить новое состояние объединенного автомата s; - выходной сигнал автомата А2 считать выходным сигналом объединенного автомата А y; - продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния; - закончить. По таблице 13 из состояния s11 по сигналу х 12 первый автомат А1 перейдет в состояние s13. На выходе автомата А1 будет сигнал y 11, который равен входному сигналу автомата А2, ( При рассмотрении работы этого и других соединений нужно учитывать, что первый индекс относится к номеру исходного автомата, а второй индекс является действительным номером входного сигнала, состояния и выходного сигнала объединенного автомата. Должно учитываться взаимно однозначное соответствие между номером выходного сигнала одного исходного автомата и номером входного сигнала другого автомата. Применительно к итоговому автомату первый индекс должен отбрасываться. Состояния s13, s21 определяют новое состояние s5, выходной сигнал уже известен, и соответствует y1. В результате последовательного соединения автоматов А1 и А2, заданных в таблицах 13 и 14 соответственно, получается результирующий автомат А. При необходимости следует составить совмещенную таблицу переходов и выходов объединенного автомата А, представленной табл. 15. Таблица 15
Параллельное соединение автоматов Параллельное соединение автоматов рассмотрим на примере схемы, представленной на рисунке 3.
Рисунок. 3 Параллельное соединение автоматов Исходные автоматы - это автоматы А1 и А2, а результирующий – автомат А, которые описываются множествами (1.7). Из рисунка 3 следует следующее равенство входных и выходных слов (сигналов) параллельного соединения автоматов:
Х1 = Х2 = Х; Y = F (Y1; Y2), S = S1 × S2. (1.14)
F – комбинационная логическая функция, реализованная на логических элементах, устанавливающая закон формирования выходного сигнала объединенного автомата А. Тогда для любого состояния объединенного автомата А S {(s1i × s2j) Î S, где s1i Î S1 а s2j Î S2} должно выполняться условие
d((s1i × s2j), х) = (d1(s1i, х1), d2(s2j, х2)), (1.15)
l ((s1i × s2j), х) = F (l1(s1i, х1), l2(s2j, х2)), (1.16)
где d1, d2 и d функции перехода первого автомата, второго автомата и объединенного автомата соответственно; l1, l2 и l - функции выхода первого автомата, второго автомата и объединенного автомата соответственно. Изложенные теоретические положения проиллюстрируем на примере автоматов Мили. Совмещенные таблицы переходов и выходов для А1, А2 представлены в табл.13 и 14 соответственно. Для параллельного соединения пусть будут заданы начальное состояние s5 (s13, s21) и входной сигнал х 2. Оба автомата работают одновременно под действием одного и того же входного сигнала х 2. Преобразователь F преобразует выходные сигналы автоматов А1 и А2 во множество выходных сигналов итогового автомата А: y = F (y а1, y а2).
Функция преобразования F отражена в табл. 16. Таблица 16
Алгоритм функционирования параллельного соединения автоматов А1 и А2 можно сформулировать следующим образом: - начать; - перебирать предыдущие состояния объединенного автомата А(s); - по состоянию s определить предыдущие состояния s1i и s2j; - по сигналу x определить данные состояния s1i и s2j, выходные сигналы y 1i и y 2j; - по s1i и s2j определить данное состояние объединенного автомата si; - по y 1i и y 2j определить данный выходной сигнал y i; - продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния; - закончить. Первый автомат А1 из состояния s13 переходит в состояние s12, и на выходе выдает сигнал y11 (табл.13), второй автомат А2 из состояния s21 переходит в состояние s22, и на выходе выдает сигнал y22 (табл. 14). Объединенный автомат переходит в новое состояние s4 (s12, s22). В соответствии с табл. 16 на выходе формируется сигнал y2. В результате параллельного соединения автоматов А1 и А2, заданных в табл. 13 и 14 соответственно, получается результирующий автомат А, совмещенная таблица переходов и выходов которого представлена в табл. 17. Таблица 17
Соединение автоматов с обратной связью Соединение автоматов с обратной связью рассмотрим на примере схемы, представленной на рисунке 4.
Рисунок 4 Соединение автоматов с обратной связью Исходные автоматы А1 и А2 и объединенный автомат А описываются множествами (1.7). Из рисунка 4 следует равенство входных и выходных слов (сигналов) при соединении автоматов с обратной связью:
Х1 = F (Х; Y2), X2 = Y1, Y = Y1.
Автоматы А1 и А2 заданы таблицами переходов и выходов, представленными в таблицами 18 и 19.
Таблица 18 Таблица 19
В соответствии с приведенными равенствами и функций переходов и выходов автоматов А1 и А2 (табл. 13 и 14) входной сигнал автомата А1 будет определяться выражением
Х1 = F1 (Х, Y2) = F (Х, d2(s2j, х2)) = F (Х, d2(s2j, l1(s1i, х1))).
Алфавитом состояний объединенного автомата S будет произведение алфавитов состояний первого S1 и второго S2 автоматов
S = S1 × S2.
Тогда для любого состояния объединенного автомата входной сигнал будет определяться некоторой функцией F1, определяющей формирование входного сигнала первого автомата. В результате соединения автоматов А1 и А2 с обратной связью, получается результирующий автомат А, совмещенную таблицу переходов и выходов которого следует составить по нижеприведенному алгоритму. В данном соединении имеется некоторый функциональный преобразователь F1 (табл. 20), являющийся автоматом без памяти, который реализует F1 отображение входных сигналов автомата А1 ко входным сигналам объединенного автомата А и выходным сигналам автомата А2.
XA1= F1 (XА, YА2).
Таблица 20
При соединении автоматов с обратной связью автомат А2, включенный в обратную связь, должен быть автоматом Мура. Таблица 18 является совмещенной таблицей переходов и выходов автомата A1, а таблица 19 – отмеченной таблицей переходов автомата А2. Алгоритм функционирования соединения автоматов с обратной связью можно сформулировать так: - начать; - перебирать предыдущие состояния объединенного автомата s; - по состоянию sj определить предыдущие состояния s1i и s2j; - по состоянию s2j определить выходной сигнал y 2j; - по входному сигналу xi и выходному сигналу y 2j определить входной сигнал автомата А1 x 1i; - по сигналу x 1i определить последующее состояние автомата А1 s1i и его выходной сигнал y 1j; - по выходному сигналу y 1j, который равен входному сигналу х2j, определить новое состояние автомата А2 s2j; - по данным состояниям s1i и s2j определить последующее состояние объединенного автомата sj; - по выходному сигналу автомата А1 y 1j определить выходной сигнал объединенного автомата y i; - продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния; - закончить. Выбираем предыдущее состояние объединенного автомата s1 (s11, s21) при входном сигнале х 1. Предыдущее состояние автомата А2 соответствует состоянию s22 и на выходе будет сигнал y22 (табл.19). По сигналам х 1 и y22 преобразователь F1 (табл.20) формирует сигнал х 11. По этому сигналу автомат А1 из предыдущего состояния s11 переходит в состояние s13 (табл. 18) и на выходе формирует сигнал y11, который соответствует выходному сигналу объединенного автомата y1 (y11 = y1). По сигналу y1 = х 21 автомат А2 из состояния s21 переходит в состояние s21 (табл. 19). Следовательно, при воздействии входного сигнала х 1 автомат А1 перейдет в состояние s13, а автомат А2 в состояние s21, что соответствует состоянию s5 объединенного автомата и на выходе будет сформирован сигнал y1. В соответствии с алгоритмом перебрав все состояния объединенного автомата А при водном воздействии Х определяется таблица переходов и выходов объединенного автомата А, которая представлена таблицей 21. Таблица 21
Соединение в сеть представляет собой комбинацию рассмотренных выше схем соединения выходы, которых связаны общей выходной функцией. Входы будут определяться входными функциями каждого автомата, устанавливающими связь между входными и выходными сигналами компонентных автоматов, образующих сеть.
|
). В соответствии с таблицей 14 по этому сигналу и исходному состоянию s21 автомат А2 перейдет в состояние s21 и на выходе выдаст сигнал y21, который будет являться выходным сигналом объединенного автомата y1 (y21 = y1).
