Рівнобіжне з'єднання
Автомати А1 = (S1, X1, Y1, d1, l1, {s01}), A2 = (S2, X2, Y2, d2, l2, {s02}) задані шістками. Входи автоматів з'єднані безпосередньо, а виходи через КСj, що реалізує перетворення j: Y1´Y2®Y, тобто КСj - вироджений третій автомат A3 = (S3, (Y1´Y2), Y, jкс, lкс, {s0j}), де S3 = {s04}, j кс: s04®s04, lкс: (Y1´Y2) = {s04}´(Y1´Y2) ~ Y1´Y2®Y.
Рис. 20.1. Рівнобіжне з'єднання автоматів
Визначення. Результуючим автоматом рівнобіжного з'єднання двох автоматів A1 і A2 є автомат А= (S, X, Y, d, l, {s0}), у якого
1. S = S1´S2, S = {sÎS| s= <s1, s2 > & s1ÎS1, & s2ÎS2}.
2. X = X1 = X2.
3. U = jкс(Y1´Y2), Y = {yÎY| y = j кс(y1, y2) & y1ÎY1 & y2ÎY2}.
4. d: S´X ® S і визначається так:
d(S´X)=(d1(S1´X1), d2 (S2´X2)), чи d(S´X)={s=d(s', x)Î d(S´X)| s'=<s'1, s'2 > & xÎX & s=<s1, s2 > & s1=d1(s'1, x) & s2=d2(s'2, x)}.
5. l: S´X®Y і визначається таким чином:
l(S´X) = jкс(l1(S1´X1), l2(S2 ´ X2 )) чи l(S´X) = {y =
l(s', х')ÎY| s' = <s'1, s'2 > & x ÎX & y = jкс(<y1, y2 >) & y1 = l1(s1’, x ) & y2 = l2(s2’, x )}.
6. s0 = <s01, s02>.
Приклад. Задані два автомати Мілі A1 і A2
Функції автомата A1 d1:S1´X®S1 & l1:S1´X®Y1
Таблиця 20.1
| S1 X | s11 | s12 | s13 |
| x1 | s11/y11 | s11/y12 | s12/y12 |
| x2 | s13/y11 | s13/y11 | s12/y11 |
Функції автомата A2 d2:S2´X®S2 & l2:S2´X®Y1
Таблиця 20.2
| S2 X | s21 | s22 |
| x1 | s21/y21 | s22/y22 |
| x2 | s22/y22 | s21/y21 |
Функції вихідного преобразователя j кс :Y1´Y2®Y
Таблиця 20.3
| Y2 Y1 | y21 | y22 |
| у11 | y1 | y2 |
| у12 | y2 | y3 |
Функція переходів результуючого автомата d:S´X®S
Таблиця 20.4
| S/S1´S2 X | s1 | S2 | s3 | s4 | s5 | s6 |
| <s11 s21> | < s11s22> | <s12s21> | <s12s22> | <s13s21> | <s13s22> | |
| x1 | s1/s11s21 | s2/s11s22 | s1/s11s21 | s2/s11s22 | s3/s12s21 | s4/s12s22 |
| x2 | s6/s13s22 | s5/s13s21 | s6/s13s22 | s5/s13s21 | s4/s12s22 | s3/s12s21 |
Функція виходів результуючого автомата l:S´X®Y
Таблиця 20.5
| S/S1´S2 X | s1 | s2 | s3 | s4 | s5 | s6 |
| <s11 s21> | < s11s22> | <s12s21> | <s12s22> | <s13s21> | <s13s22> | |
| x1 | y1/y11y21 | y2/y11y22 | y2/y12y21 | y3/y12y22 | y2/y12y21 | y3/y12y22 |
| x2 | y2/y11y22 | y1/y11y21 | y2/y11y22 | y1/y11y22 | y2/y11y22 | y1/y11y21 |
Початкові стани s01= s11, s02= s21 для A1 і A2, для A – початковий стан - s1 =<s11, s21>