Рівнобіжне з'єднання

Автомати А₁ = (S₁, X₁, Y₁, d₁, l₁, {s₀₁}), A₂= (S₂, X₂, Y₂, d₂, l₂, {s₀₂}) задані шістками. Входи автоматів з'єднані безпосередньо, а виходи через КС_j, що реалізує перетворення j: Y₁´Y₂®Y_,тобто КС_j - вироджений третій автомат A₃ = (S₃, (Y₁´Y₂), Y, j_кс, l_кс, {s₀_j}), де S₃ = {s₀₄}, j_кс: s₀₄®s₀₄, l_кс: (Y₁´Y₂) = {s₀₄}´(Y₁´Y₂) ~ Y₁´Y₂®Y.

Рис. 20.1. Рівнобіжне з'єднання автоматів

Визначення. Результуючим автоматом рівнобіжного з'єднання двох автоматів A₁ і A₂ є автомат А= (S, X, Y, d, l, {s₀}), у якого

1. S = S₁´S₂, S = {sÎS| s= <s_1, s₂> & s₁ÎS₁, & s₂ÎS₂}.

2. X = X₁ = X_2.

3. U = j_кс(Y₁´Y₂), Y = {yÎY| y = j_кс(y_1, y₂) & y₁ÎY₁ & y₂ÎY₂}.

4. d: S´X ® S і визначається так:

d(S´X)=(d₁(S₁´X₁), d₂(S₂´X₂)), чи d(S´X)={s=d(s', x)Î d(S´X)| s'=<s'_1, s'₂> & xÎX & s=<s_1, s₂> & s₁=d₁(s'₁, x) & s₂=d₂(s'₂, x)}.

5. l: S´X®Y і визначається таким чином:

l(S´X) = j_кс(l₁(S₁´X₁), l₂(S₂´ X₂)) чи l(S´X) = {y =
l(s', х')ÎY| s' = <s'₁, s'₂> & x ÎX & y = j_кс(<y_1,y₂>) & y₁ = l₁(s₁^’, x) & y₂ = l₂(s₂^’, x)}.

6. s₀ = <s_01, s₀₂>.

Приклад. Задані два автомати Мілі A₁і A₂

Функції автомата A₁ d₁:S₁´X®S₁& l₁:S₁´X®Y₁

Таблиця 20.1

S1 X	s11	s12	s13
x1	s11/y11	s11/y12	s12/y12
x2	s13/y11	s13/y11	s12/y11

Функції автомата A₂ d₂:S₂´X®S₂& l₂:S₂´X®Y₁

Таблиця 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