21.1. Мережі автоматів

Мережа автоматів – це математична модель, що описує спільну роботу сукупності n автоматів. Мережа автоматів узагальнює всі можливі способи з'єднання автоматів.

Визначення. Мережа автоматів – це шістка N = (X, {A_i}, Y, {f_i’}, {f_i”}, g), де X иY – відповідно вхідний і вихідний алфавіти мережі N_i; {A_i} - множина компонентних автоматів мережі (і =1, n, іI); {f_i’} – множина функцій з'єднань компонентних автоматів; f_i’:Y_jХ'_і, j {1, n}, { f_i”} - множина вхідних функцій компонентних автоматів; f_i”:XХ''_і; g - вихідна функція мережі g:(_i=1ⁿY_i)XY.

Компонентні автомати {A_i} утворюють базис мережі, а множина функцій {f_i}, {_і}, g - утворять структуру мережі. Компонентний автомат мережі представляється четвіркою

A_i = (S_i, X_i  _і,{s_0і}).

Компонентний автомат – це автомат Мура, в якому вихідні сигнали ототожнені з його станами. Для автомата Мура, в якому вихідні сигнали ототожнені з його станами, раніш використалася інша, більш відома назва як контекстного автомата, або напівавтомата, або автомата Медведєва.

Рис. 21.1. Компонентний автомат мережі

X_i = Х'_іХ''_і,, якщо Х'_і  

Х''_і, якщо Х'_і = ,

де Х'_і – внутрішній вхідний алфавіт А_і; Х''_і – зовнішній вхідний алфавіт А_і; _і:S_iX_iS_i, f_i’:(_i=1ⁿY_j)Х'_і, де і, j{1, n} – функція з'єднання, f_i”:XХ''_і – вхідна функція A_i.

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

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

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

A_N = (S_N, X_N, Y_N, _N, _N, {s_0N}),

де X_N = X, S_N = (_i=1ⁿS_i), і{1, n}, Y_N = Y.

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

_N: S_NX_NS_N чи (S_NX_N) = {s_nj = (s'_nj, x)(S_NX_N)| s_nj = <s_1j, s_nj, … s_ij, … s_nj> & s’_ij = <s’_1j, s’_2j, … s’_ij, … s’_nj> & s_ij, s’_ijS_i для всіх і{1, n}, & s_ij = _і(s'_іj, <f_i(y_1k, y_2k, …y_ik, …y_nk), (X_N)) & y_ik  s’_ij, для всіх і{1, n}}.

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

_N: S_NX_NY_N чи _N(S_NX_N) = {y = _N(s'_nj, X_N_N(S_NX_N)| yY_N & X_N X_N & s'_nj = <s'_1j, s'_2j, …s’_ij, …s’_nj> & s’_ijS_i для всіх і{1, n} & y = g(<у'_1k, у'_2k, …y’_ik, …y’_nk>, X_N) & y’_ik  s’_ij для всіх і{1, n}}.

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

_N: S_NX_NY_N чи _N(S_N) = {y = _N(s'_nj_N(S_N)| yY_N & s'_nj =<s'_1j, s'_2j, …s’_ij, …s’_nj> & s’_ijS_i для всіх і{1, n} & y = g<s'_1j, s'_2j, …s’_ij, …s’_nj> = g_N(<y’_1k, y’_2k, …y’_{ik, …} y’_nk > & y’_ik  s’_ij для всіх і{1, n}}.

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

f₁ =  (не визначена)

f₂:Y₁Y₃X’₂ чи X’₂ = f₂(Y₁Y₃)

f₃:Y₂X’₃ чи X’₃ = f₃(Y₂)

g:Y₂Y₃Y чи Y = g(Y₂Y₃)

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

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

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

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

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

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

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

Список літератури Основна

1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.305-335.

2. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41; 74-82; 118-132.

3. Кук Л., Бейз Г. Компьютерная математика. – М: Наука, 1990. -С.302-335.

Додаткова

4. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.160-204.

5. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. - С.75-80.

Для практичних занять

6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2002. –С. 54-57.

7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.190-208.