Послідовне з'єднання двох автоматів

Автомати A₁ = (S_1, X_1, Y_1,d _1, l_1, {s₀₁}), A₂ = (S_2, X_2, Y_2,d _2, l_2, {s₀₂}) задані шістками. Вихід першого автомата з'єднаний безпосередньо з входом другого автомата, тобто Y₁ = X₂.

Рис. 20.2. Послідовне з'єднання автоматів

Визначення. Результуючим автоматом послідовного з'єднання двох автоматів A₁ і 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₁.

3. Y₁ = X₂.

4. Y = Y₂.

5. d: S´X®S і визначається в такий спосіб:

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

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

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

7. s₀ = <s₀₁, s₀₂>.

Приклад. Задані автомати Мілі A₁ і A₂ з попереднього прикладу.

Функція переходів результуючого автомата d:S´X®S

Таблиця 20.6

S/S1´S2 X	s1	s2	s3	s4	s5	s6
s11s21	s11s22	s12s21	s12s22	s13s21	s13s22
x1	s1/s11s21	s2/s11s22	s2/s11s22	s1/s11s21	s4/s12s22	s3/s12s21
x2	s5/s13s21	s6/s13s22	s5/s13s21	s6/s13s22	s3/s12s21	s4/s12s22

Функція виходів результуючого автомата l:S´X®Y

Таблиця 20.7

S/S1´S2 X	s1	s2	s3	s4	s5	s6
s11s21	s11s22	s12s21	s12s22	s13s21	s13s22
x1	y1/y11y21	y2/y11y22	y2/y12y21	y3/y12y22	y2/y12y21	y3/y12y22
x2	y1/y11y21	y2/y11y22	y1/y11y21	y2/y11y22	y1/y11y21	y2/y11y22

Початкові стани для A₁ і A₂ - s₀₁ = s₁₁ і s₀₂ = s_21, для А початковий стан – s₁ = <s₁₁, s₂₁>