double arrow

Еквівалентні автомати мережі


Для мережі з n компонентних автоматів можна побудувати еквівалентний автомат А мережі

Рис. 21.2. Мережа з n компонентних автоматів

AN = (SN, XN, YN, dN, lN, {s0N}),

де XN = X, SN = (´i=1nSi), іÎ{1, n}, YN = Y.

Функція dN визначається в такий спосіб

dN: SN´XN®SN чи d(SN´XN) = {snj = d(s'nj, x)Îd(SN´XN)| snj = <s1j, snj, … sij, … snj> & s’ij = <s’1j, s’2j, … s’ij, … s’nj> & sij, s’ijÎSi для всіх іÎ{1, n}, & sij = dі(s'іj, <fi(y1k, y2k, …yik, …ynk),
j(XN)) & yik @ s’ij, для всіх іÎ{1, n}}.

Функція lN для автомата Мілі визначається в такий спосіб

lN: SN´XN®YN чи lN(SN´XN) = {y = lN(s'nj, XNÎdN(SN´XN)| yÎYN & XNÎ XN & s'nj = <s'1j, s'2j, …s’ij, …s’nj> & s’ijÎSi для всіх іÎ{1, n} & y = g(<у'1k, у'2k, …y’ik, …y’nk>, XN) & y’ik @ s’ij для всіх іÎ{1, n}}.

Функція lN для автомата Мура визначається в такий спосіб

lN: SN´XN®YN чи lN(SN) = {y = lN(s'njÎlN(SN)| yÎYN & s'nj =<s'1j, s'2j, …s’ij, …s’nj> & s’ijÎSi для всіх іÎ{1, n} & y = g<s'1j, s'2j, …s’ij, …s’nj> = gN(<y’1k, y’2k, …y’ik, … y’nk > & y’ik @ s’ij для всіх
іÎ{1, n}}.

Приклад. Мережа з трьома компонентними автоматами.

f1 = Æ (не визначена)

f2:Y1´Y3®X’2 чи X’2 = f2(Y1´Y3)

f3:Y2®X’3 чи X’3 = f3(Y2)

g:Y2´Y3®Y чи Y = g(Y2´Y3)

Рис. 21.3. Мережа з трьома компонентними автоматами

Контрольні запитання

1. Що є мережею автоматів, що узагальнює мережа автоматів?

2. Що є компонентним автоматом?

3. Яка різниця між компонентним автоматом та звичайним напівавтоматом?

4. Що є еквівалентним автоматом для мережі автоматів?

5. Як визначити функції переходів та вихідів для еквівалентного автомата мережі автоматів?


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