double arrow

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


Автомати A1 = (S1, X1, Y1,d 1, l1, {s01}), A2 = (S2, X2, Y2,d 2, l2, {s02}) задані шістками. Вихід першого автомата з'єднаний безпосередньо з входом другого автомата, тобто Y1 = X2.

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

Визначення. Результуючим автоматом послідовного з'єднання двох автоматів A1 і A2 називається автомат A = (S, X, Y,d , l, {S0}), у якого

1. S = S1´ S2, тобто S = {sÎS| s= < s1, s2> & s1, ÎS1 & s2 Î S2 }.

2. X = X1.

3. Y1 = X2.

4. Y = Y2.

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

d(S´X) = (S´X) = (d(S1´X1), (d2(S2´X2)) чи d(S´X) = {s = d(s, x)Îd(S´X)| s' = <s1, s2 > & s= <s1, s2> & x Î X & s1 = = d(s1, x) & s2 = d2(s2, l1(s1, x)} .

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

l(S´X) = (S´X) = l2(S2´l1(S1´X )) чи l(S´X) = {y=
=l(s, x)ÎY| s' = <s1, s2> & xÎX & y = l2(s2, l1(s1, x))} .

7. s0 = <s01, s02>.

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

Функція переходів результуючого автомата 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

Початкові стани для A1 і A2 - s01 = s11 і s02 = s21, для А початковий стан – s1 = <s11, s21>


Сейчас читают про: