1. Паралельне з'єднання (рис. 3.11). Різняться з'єднання з загальними і роздільними входами (алфавітами).
S1
S1
А1
V1
V1
A
S2
S2
A2
V2
V2
Рис. 3.11 - Паралельне з'єднання автоматів
Для випадку, коли паралельне з'єднання автоматів представлено парою автоматів S1 = {A1, Q1, V1, 1, 1}; S2 = {A2, Q2, V2, 2, 2} то його можна розглядати як один автомат S = {A, Q, V, , }, що визначається в такий спосіб: A = A1A2, Q = Q1Q2, V = V1V2. Таким чином, вхідний символ автомата S - це пара символів: a = (a1, a2), стан автомата S - це пару станів: q = (q1, q2), де q1 Q1, q2 Q2. Далі (q, a) = ((q1, q2), (a1, a2)) = (1(q1, a1), 2(q2, a2)), тобто зміна станів відбувається незалежно й одночасно. Аналогічно: (q, a) = (1(q1, a1), 2(q2, a2)) = (v1, v2), де v1 V1; v2 V2. При цьому автомат S називається прямим добутком автоматів S1 і S2.
Для другого варіанта паралельного з'єднання вхідні алфавіти S1, S2 і S збігаються. Тому (q, a) = (1(q1, a), 2(q2, a)).
Послідовне з'єднання автоматів показане на рис. 3.12.
S1
S2
A1 A2=V1
V2
Рис. 3.12 - Послідовне з'єднання автоматів
Цю мережу можна описати як автомат S = {A, Q, V, , }, причому A=A1, V=V2, V1=A2 і Q = Q1 Q2. Для визначення і істотна затримка функції 1. Якщо затримка 1 дорівнює нулю, то
1(q1(t), a(t)) = V1(t);
q(t+1) = (q1 (t+1), q2(t+1)) =
= (1(q1(t), a(t)), 2(q2(t), 1(q1(t), a(t)))).
Вираз в лівій частині залежить тільки від q(t) і a(t) і, отже, визначає q(t+1) як функцію від цих змінних. Ця функція і є функція для S.
Якщо ж час затримки 1 дорівнює одиниці, то одержимо:
1(q1(t), a(t)) = V1(t+1);
q(t+1) = (1(q1(t), a(t)), 2(q2(t), 1(q1(t-1), a(t-1)))).
Таким чином, залежність тільки від попереднього такту не утворюється і необхідно ускладнювати автоматний опис такої мережі.
Методи одержання єдиного автоматного опису для мереж з автоматів називаються методами композиції автоматів. Ці методи вирішують задачу аналізу мереж, оскільки дослідження поводження мереж зручно проводити при наявності автоматного опису: таблиці переходів або графа переходів.
3.10. Приклад синтезу кінцевого автомата
Нехай кінцевий автомат заданий сполученою таблицею переходів - виходів.
Таблиця переходів-виходів кінцевого автомата.
X(n) (стан / вихід)
y(m) 0 1 2 3
-
0
2/0
2/0
0/0
0/1
1
1/1
1/0
0/1
1/1
2
1/0
0/1
2/1
0/0
Перетворимо вихідну таблицю в спеціальну форму з виділенням вхідних - вихідних сигналів і внутрішніх станів.
Таблиця 3.11 - Проміжна таблиця
|
Входи |
x(n) |
000 111 222 333 |
|
Поточні стани |
s(n) |
012 012 012 012 |
|
Наступні стани |
s(n+1) |
211 210 002 010 |
|
Виходи |
y(n) |
010 001 011 110 |
Замінюючи десяткові числа на двійкві, одержимо таблицю істинності, у якій значення x(n), s(n), s(n+1), y(n) подані в двійковому коді.
Таблиця 3.12 - Таблиця істинності кінцевого автомата
|
x(n) |
s(n) |
s(n+1) |
y(n) | |||
|
x1(n) |
x2(n) |
s1(n) |
s2(n) |
s1(n+1) |
s2(n+1) |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
* |
* |
* |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
* |
* |
* |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
* |
* |
* |
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
* |
* |
* |
Граф кінцевого автомата буде мати вигляд, показаний на рис. 3.13.
0/1
1/0
3/1
2/1
1
0
1/1
3/0 0/0
2
/0
3/1
0/0
0/1 2 2/1
Рис. 3.13 - Граф синтезованого кінцевого автомата
Вихідні функції для синтезу автомата по таблиці 3.12 буде мати вигляд:
s1(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
y(n) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n).
Мінімізуємо дані функції за допомогою карт Карно.
Для s1(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
001
1
01
11
10
1
Для s2(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
00
011
1
1
11
10
1
Для y(n).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
001
011
1
1
11
10
1
1
Результати мінімізації представимо у вигляді:
s1(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
y(n)=x2(n)s1(n)s2(n) x1(n)x2(n)s1(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n).
Структура автомата в загальному виді подана на такому рис. 3.14.
