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

Мережа автоматів – це математична модель, що описує спільну роботу сукупності 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}, {y_і}, g - утворять структуру мережі. Компонентний автомат мережі представляється четвіркою

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

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

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

X_i = Х'_і´Х''_і,, якщо Х'_і ¹ Æ

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

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