Прикладная теория цифровых автоматов
1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА
1.1. Побудова ГСА
По описах граф-схем, приведених в завданні до курсової роботи,
побудуємо ГСА Г1-Г5 (мал. 1.1-1.5), додавши початкові і кінцеві вершини і
замінивши кожний оператор Yi операторною вершиною, а кожну умову Xi -
умовною.
1.2. Методика об'єднання ГСА
У ГСА Г1-Г5 є однакові ділянки, тому побудова автоматів за ГСА Г1-Г5
приведе до невиправданих апаратурних витрат. Для досягнення оптимального
результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати
число операторних і умовних вершин. Заздалегідь помітимо операторн( вершини
в початкових ГСА, керуючись сл(дуючими правилами:
1) однакові вершини Yi в різних ГСА відмічаємо однаковими мітками Aj;
2) однакові вершини Yi в межах однієї ГСА відмічаємо різними
мітками Aj;
3) у всіх ГСА початкову вершину помітимо як А0, а кінцеву - як
Ak.
На наступному етапі кожн(й ГСА поставимо у
відповідність набір змінних Pn( {P1...Pq}, де q=]log2N[, N -к(льк(сть
ГСА. Означувальною для ГСА Гn ми будемо називати кон`юнкцию
Pn=p1e(...(pqn е({0,1}, причому p0=(р, p1=р. Об'єднана ГСА повинна
задовольняти сл(дуючим вимогам:
1) якщо МК Ai входить хоча б в одну часткову ГСА, то вона входить і в
об'єднану ГСА Г0, причому тільки один раз;
2) при підстановці набору значень (е1...en), на якому Pq=1 ГСА Г0
перетворюється в ГСА, рівносильну частков(й ГСА Гq.
При об'єднанні ГСА виконаємо сл(дуючі етапи:
-сформуємо часткові МСА М1 - М5, що відповідні ГСА Г1 - Г5;
- сформуємо об'єднану МСА М0;
- сформуємо системи дужкових формул переходу ГСА Г0;
- сформуємо об'єднану ГСА Г0.
1.3. Об'єднання часткових ГСА
Часткові МСА М1-М5 побудуємо по ГСА Г1-Г5 (мал.1.1) відповідно. Рядки
МСА відмітимо всіма мітками Ai, що входять до ГСА, крім кінцевої Ak.
ПОЧАТОК A0
1
0 X1 1
2
A1
3
0
4 X2
A2 1
5
A3
6
A4
7
A5
8
A6
9
A7
10
A8
К(НЕЦь Ak
Мал.1.1. Часткова граф-схема алгоритму Г1
ПОЧАТОК A0
1
A1
2
A7
0 3 1
X3
4 5
A9 A6
6 7
A10 A12
8 9
A3 A22
10
A11
К(НЕЦЬ Ak
Мал.1.2. Часткова граф-схема алгоритму Г2
ПОЧАТОК A0
1
A11
0 2 1
X1
3 4
A15 A16
6
5 1
X3 A12
0
7 8
A6 A13
К(НЕЦЬ Аk
Мал.1.3. Часткова граф-схема алгоритму Г3
ПОЧАТОК A0
1
0 1
X1
2
A13
3
A9
4
A8
5
1 X2
6 0
A17
7
A6
8
A2
9
A18
К(НЕЦЬ Ak
Мал.1.4. Часткова граф-схема алгоритму Г4
ПОЧАТОК A0
1
A1
2
A6
3
A19
4
0 1
X1
5
0 X2
1
6
A20
7
A17
8
A2
9
A21
К(НЕЦЬ Ak
Мал.1.5. Часткова граф-схема алгортиму Г5
Стовпці МСА відмітимо всіма мітками Ai, що входять до ГСА, крім
початкової A0. На перетині рядка Ai і стовпця Aj запишемо формулу переходу
fij від оператора Ai до оператора Aj. Ця функція дор(вню( 1 для безумовного
переходу або кон`юнкц(( логічних умов, відповідних виходам умовних вершин,
через які проходить шлях з вершини з м(ткою Ai у вершину з м(ткою Aj.
За методикою об'єднання закодуємо МСА таким чином:
Таблиця 1.1
Кодування
МСА
|МСА |P1P2P3 |
|М1 |0 0 0 |
| |((p1(p2(p3) |
|М2 |0 0 1 |
| |((p1(p2p3) |
|М3 |0 1 0 |
| |((p1p2(p3) |
|М4 |0 1 1 |
| |((p1p2p3) |
|М5 |1 0 0 |
| |(p1(p2(p3) |
Частков( МСА М1-М5 наведен( в табл.1.2-1.6
Таблиця 1.2
Часткова МСА М1
| | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | Ak |
| A0 | (x1 |(x1(x2| x1x2 | | | | | | |
| A1 | | 1 | | | | | | | |
| A2 | | | | | | 1 | | | |
| A3 | | | | 1 | | | | | |
| A4 | | | | | 1 | | | | |
| A5 | | | | | | 1 | | | |
| A6 | | | | | | | 1 | | |
| A7 | | | | | | | | 1 | |
| A8 | | | | | | | | | 1 |
Таблиця 1.3
Часткова МСА М2
| | A1 | A3 | A6 | A7 | A9 | A10 | A11 | A12 | A22 | Ak |
| A0 | 1 | | | | | | | | | |
| A1 | | | | 1 | | | | | | |
| A3 | | | | | | | 1 | | | |
| A6 | | | | | | | | 1 | | |
| A7 | | | x3 | | (x3 | | | | | |
| A9 | | | | | | 1 | | | | |
| A10 | | 1 | | | | | | | | |
| A11 | | | | | | | | | | 1 |
| A12 | | | | | | | | | 1 | |
| A22 | | | | | | | | | | 1 |
Таблиця 1.4
Часткова МСА М3
| | A6 | A12 | A13 | A14 | A15 | A16 | Ak |
| A0 | | | | 1 | | | |
| A6 | | | | | | | 1 |
| A12 | | | 1 | | | | |
| A13 | | | | | | | 1 |
| A14 | | | | | (x1 | x1 | |
| A15 | x3 | | | | | | (x3 |
| A16 | | 1 | | | | | |
Таблиця 1.5
Часткова МСА М4
| | A2 | A6 | A8 | A9 | A13 | A17 | A18 | Ak |
| A0 | | | (x1 | | x1 | | | |
| A2 | | | | | | | 1 | |
| A6 | 1 | | | | | | | |
| A8 | | | | | | x2 | | (x2 |
| A9 | | | 1 | | | | | |
| A13 | | | | 1 | | | | |
| A17 | | 1 | | | | | | |
| A18 | | | | | | | | 1 |
Таблиця 1.6
Часткова МСА М5
| | A1 | A2 | A6 | A17 | A19 | A20 | A21 | Ak |
| A0 | 1 | | | | | | | |
| A1 | | | 1 | | | | | |
| A2 | | | | | | | 1 | |
| A6 | | | | | 1 | | | |
| A17 | | 1 | | | | | | |
| A19 | | x1(x2| | | | x1x2 | (x1 | |
| A20 | | | | 1 | | | | |
| A21 | | | | | | | | 1 |
На наступному етапі побудуємо об'єднану МСА М0, в як(й рядки
відмічені всіма мітками Аi, крім Аk, а стовпці - всіма, крім А0. На
перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка
формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-
формула переходу з вершини Аi у вершину Аj для n-о( ГСА. Наприклад,
формула переходу А0(А1 буде мати вигляд F0,1=(x1(p1(p2(p3+ (p1(p2p3+
+p1(p2(p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми
маємо можливість мінімізувати формули переходу таким чином: розглядаючи
ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому
зм(нн( p1..pq не змінюють своїх значень під час проходу по ГСА. Таким
чином, якщо у вершину Аi перехід завжди здійснюється при незмінному
значенні pq, то це значення pq в рядку Аi замінимо на “1", а його
інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при
незмінному значенні (p1 і (p2, отже в рядку А3 (p1 і (p2 замінимо на
“1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=(p3,
F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА
М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0.
Формулою переходу будемо називати сл(дуюче вираження:
Ai(Fi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з
мінімізованої МСА. У нашому випадку отримаємо сл(дуючу систему формул:
A0((x1(p1(p2(p3A1+(p1(p2p3A1+p1(p2(p3A1+x1(x2(p1(p2(p3A2+x1x2(p1(p2(p3A3
+
+(x1(p1p2p3A8+x1(p1p2p3A13+(p1p2(p3A14
A1((p1(p3A2+p1(p3A6+(p1p3A7
A2((p1(p2(p3A6+(p1p2p3A18+p1(p2p3A21
A3((p3A4+p3A11
A4(A5
A5(А6
Таблиця
1.7
Об`(днана МСА Мo
| | | | | | | | | | | | | | | | | | | | | | | | |
| |A1 |A2 |A3 |A4 |A5 |A6 |A7 |A8 |A9 |A10 |A11 |A12 |A13 |A14 |A15 |A16 |A17 |A18 |A19 |A20 |A21 |A22 |Ak |
| |_ _ _ | _ _ | _ | | | | |_ _ | | | | | _ |_ | | | | | | | | | |
| |_ |_ _ |_ _ | | | | |x1p1p| | | | |x1p1p2|_ | | | | | | | | | |
|A0 |x1p1p2|x1x2p1|x1x2p1| | | | |2p3 | | | | |p3 |p1p2| | | | | | | | | |
| |p3+ |p2p3 |p2p3 | | | | | | | | | | |p3 | | | | | | | | | |
| |_ _ | | | | | | | | | | | | | | | | | | | | | | |
| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |
| |3+ | | | | | | | | | | | | | | | | | | | | | | |
| |_ _ | | | | | | | | | | | | | | | | | | | | | | |
| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |
| |3 | | | | | | | | | | | | | | | | | | | | | | |
| | |_ _ _ | | | | _ _|_ _ | | | | | | | | | | | | | | | | |
|A1 | |p1p2p3| | | | | | | | | | | | | | | | | | | | | |
| | | | | | |p1p2p|p1p2| | | | | | | | | | | | | | | | |
| | | | | | |3 |p3 | | | | | | | | | | | | | | | | |
| | | | | | |_ _ _| | | | | | | | | | | |_ | | | _ _| | |
|A2 | | | | | | | | | | | | | | | | | |p1p2p| | | | | |
| | | | | | |p1p2p| | | | | | | | | | | |3 | | |p1p2p| | |
| | | | | | |3 | | | | | | | | | | | | | | |3 | | |
| | | | |_ _ | | | | | | |_ _ | | | | | | | | | | | | |
|A3 | | | |_ | | | | | | |p1p2p| | | | | | | | | | | | |
| | | | |p1p2| | | | | | |3 | | | | | | | | | | | | |
| | | | |p3 | | | | | | | | | | | | | | | | | | | |
| | | | | |_ _ | | | | | | | | | | | | | | | | | | |
|A4 | | | | |_ | | | | | | | | | | | | | | | | | | |
| | | | | |p1p2| | | | | | | | | | | | | | | | | | |
| | | | | |p3 | | | | | | | | | | | | | | | | | | |
| | | | | | |_ _ _| | | | | | | | | | | | | | | | | |
|A5 | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | |p1p2p| | | | | | | | | | | | | | | | | |
| | | | | | |3 | | | | | | | | | | | | | | | | | |
| | |_ | | | | |_ _ | | | | |_ _ | | | | | | | _ _ | | | |_ _ |
|A6 | |p1p2p3| | | | |_ | | | | |p1p2p| | | | | | |p1p2p3| | | |p1p2p3|
| | | | | | | |p1p2| | | | |3 | | | | | | | | | | | |
| | | | | | | |p3 | | | | | | | | | | | | | | | | |
| | | | | | | _ _| |_ _ _|_ _ _ | | | | | | | | | | | | | | |
|A7 | | | | | | | | |x3p1p2| | | | | | | | | | | | | | |
| | | | | | |x3p1p| |p1p2p|p3 | | | | | | | | | | | | | | |
| | | | | | |2p3 | |3 | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | _ | | | | | |_ _ _ |
|A8 | | | | | | | | | | | | | | | | |x2p1p2| | | | | |p1p2p3|
| | | | | | | | | | | | | | | | | |p3 | | | | | |+ |
| | | | | | | | | | | | | | | | | | | | | | | |_ _ |
| | | | | | | | | | | | | | | | | | | | | | | |+x2p1p|
| | | | | | | | | | | | | | | | | | | | | | | |2p3 |
| | | | | | | | |_ | |_ _ | | | | | | | | | | | | | |
|A9 | | | | | | | |p1p2p| |p1p2p| | | | | | | | | | | | | |
| | | | | | | | |3 | |3 | | | | | | | | | | | | | |
| | | |_ _ | | | | | | | | | | | | | | | | | | | | |
|A10| | |p1p2p3| | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |_ _ |
|A11| | | | | | | | | | | | | | | | | | | | | | |p1p2p3|
| | | | | | | | | | | | | |_ _ | | | | | | | | |_ _ | |
|A12| | | | | | | | | | | | |p1p2p3| | | | | | | | |p1p2p3| |
| | | | | | | | | |_ | | | | | | | | | | | | | |_ _ |
|A13| | | | | | | | |p1p2p3| | | | | | | | | | | | | |p1p2p3|
| | | | | | | | | | | | | | | |_ _ | _ | | | | | | | |
|A14| | | | | | | | | | | | | | |_ |_ | | | | | | | |
| | | | | | | | | | | | | | | |x1p1p2|x1p1p| | | | | | | |
| | | | | | | | | | | | | | | |p3 |2p3 | | | | | | | |
| | | | | | | _ | | | | | | | | | | | | | | | | |_ _ |
|A15| | | | | |_ | | | | | | | | | | | | | | | | |_ |
| | | | | | |x3p1p| | | | | | | | | | | | | | | | |x3p1p2|
| | | | | | |2p3 | | | | | | | | | | | | | | | | |p3 |
| | | | | | | | | | | | |_ _| | | | | | | | | | | |
|A16| | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | |p1p2p| | | | | | | | | | | |
| | | | | | | | | | | | |3 | | | | | | | | | | | |
| | | _ _ | | | |_ | | | | | | | | | | | | | | | | | |
|A17| | | | | |p1p2p| | | | | | | | | | | | | | | | | |
| | |p1p2p3| | | |3 | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |_ |
|A18| | | | | | | | | | | | | | | | | | | | | | |p1p2p3|
| | | _ | | | | | | | | | | | | | | | | | | _|_ _| | |
|A19| |_ _ | | | | | | | | | | | | | | | | | |_ |_ | | |
| | |x1x2p1| | | | | | | | | | | | | | | | | |x1x2p1p|x1p1p| | |
| | |p2p3 | | | | | | | | | | | | | | | | | |2p3 |2p3 | | |
| | | | | | | | | | | | | | | | | | _ _ | | | | | | |
|A20| | | | | | | | | | | | | | | | |p1p2p3| | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | _ _ |
|A21| | | | | | | | | | | | | | | | | | | | | | |p1p2p3|
| | | | | | | | | | | | | | | | | | | | | | | |_ _ |
|A22| | | | | | | | | | | | | | | | | | | | | | |p1p2p3|
Таблиця
1.8
Об`(днана
м(н(м(зована МСА Мo
| | | | | | | | | | | | | | | | | | | | | | | | |
| |A1 |A2 |A3 |A4 |A5 |A6 |A7 |A8 |A9 |A10 |A11 |A12 |A13 |A14 |A15 |A16 |A17 |A18 |A19 |A20 |A21 |A22 |Ak |
| |_ _ _ | _ _ | _ | | | | |_ _ | | | | | _ |_ | | | | | | | | | |
| |_ |_ _ |_ _ | | | | |x1p1p| | | | |x1p1p2|_ | | | | | | | | | |
|A0 |x1p1p2|x1x2p1|x1x2p1| | | | |2p3 | | | | |p3 |p1p2| | | | | | | | | |
| |p3+ |p2p3 |p2p3 | | | | | | | | | | |p3 | | | | | | | | | |
| |_ _ | | | | | | | | | | | | | | | | | | | | | | |
| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |
| |3+ | | | | | | | | | | | | | | | | | | | | | | |
| |_ _ | | | | | | | | | | | | | | | | | | | | | | |
| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |
| |3 | | | | | | | | | | | | | | | | | | | | | | |
| | | _ _ | | | | _ |_ | | | | | | | | | | | | | | | | |
|A1 | |p1p3 | | | | |p1p3| | | | | | | | | | | | | | | | |
| | | | | | |p1p3 | | | | | | | | | | | | | | | | | |
| | | | | | |_ _ _| | | | | | | | | | | |_ | | | _ _| | |
|A2 | | | | | | | | | | | | | | | | | |p1p2p| | | | | |
| | | | | | |p1p2p| | | | | | | | | | | |3 | | |p1p2p| | |
| | | | | | |3 | | | | | | | | | | | | | | |3 | | |
| | | | | _ | | | | | | | | | | | | | | | | | | | |
|A3 | | | |p3 | | | | | | |p3 | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A4 | | | | |1 | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A5 | | | | | |1 | | | | | | | | | | | | | | | | | |
| | | _ | | | | |_ _ | | | | |_ _ | | | | | | | _ _ | | | |_ _ |
|A6 | |p1p2p3| | | | |_ | | | | |p1p2p| | | | | | |p1p2p3| | | |p1p2p3|
| | | | | | | |p1p2| | | | |3 | | | | | | | | | | | |
| | | | | | | |p3 | | | | | | | | | | | | | | | | |
| | | | | | | | | _ | _ | | | | | | | | | | | | | | |
|A7 | | | | | |x3p3 | |p3 |x3p3 | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |_ _ |
|A8 | | | | | | | | | | | | | | | | |x2p2p3| | | | | |p2p3+ |
| | | | | | | | | | | | | | | | | | | | | | | |_ |
| | | | | | | | | | | | | | | | | | | | | | | |+x2p2p|
| | | | | | | | | | | | | | | | | | | | | | | |3 |
| | | | | | | | | | | _ | | | | | | | | | | | | | |
|A9 | | | | | | | |p2 | |p2 | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A10| | |1 | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A11| | | | | | | | | | | | | | | | | | | | | | |1 |
| | | | | | | | | | | | | | _ | | | | | | | | |_ | |
|A12| | | | | | | | | | | | |p2p3 | | | | | | | | |p2p3 | |
| | | | | | | | | | | | | | | | | | | | | | | | _ |
|A13| | | | | | | | |p3 | | | | | | | | | | | | | |p3 |
| | | | | | | | | | | | | | | | _ | | | | | | | | |
|A14| | | | | | | | | | | | | | |x1 |x1 | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | _ |
|A15| | | | | |x3 | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |x3 |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A16| | | | | | | | | | | |1 | | | | | | | | | | | |
| | | _ _ | | | |_ | | | | | | | | | | | | | | | | | |
|A17| | | | | |p1p2p| | | | | | | | | | | | | | | | | |
| | |p1p2p3| | | |3 | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A18| | | | | | | | | | | | | | | | | | | | | | |1 |
| | | _ | | | | | | | | | | | | | | | | | | | _ | | |
|A19| | | | | | | | | | | | | | | | | | | |x1x2 | | | |
| | |x1x2 | | | | | | | | | | | | | | | | | | |x1 | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A20| | | | | | | | | | | | | | | | |1 | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A21| | | | | | | | | | | | | | | | | | | | | | |1 |
| | | | | | | | | | | | | | | | | | | | | | | | |
|A22| | | | | | | | | | | | | | | | | | | | | | |1 |
A6((p1p2p3A2+(p1(p2(p3A7+(p1(p2p3A12+p1(p2(p3A19+(p1p2(p3Ak
A7(x3p3A6+(p3A8+(x3p3A9
A8(x2p2p3A17+(p2(p3Ak+(x2p2p3Ak
A9(p2A8+(p2A10
A10(A3
A11(Ak
A12((p2p3A22+p2(p3A13
A13(p3A9+(p3Ak
A14((x1A15+x1A16
A15(x3A6+(x3Ak
A16(A12
A17(p1(p2(p3A2+(p1p2p3A6
A18(Ak
A19(x1(x2A2+x1x2A20+(x1A21
A20(A17
A21(Ak
A22(Ak
При побудові системи дужкових формул переходу необхідно кожну формулу
привести до вигляду Аx1+В(x1, де А і В -деякі вирази, а x1 і (x1-логічн(
умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13,
А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в
інших є вирази виду Аn(xj(А) +(xjpi(В). Тут pi відповідає чекаючій вершині
(мал.1.6). Подібних вершин в об'єднан(й ГСА бути не повинно. Для їх
усунення скористаємося сл(дуючим правилом: додавання виразу [PqАn] не
змінить формулу, якщо набір Pq не використовується для кодування ГСА або
вершина Аn в(дсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні
набори, ми отримаємо можливість за допомогою елементарних перетворень
звести формули до необхідного вигляду. Наприклад, формула
A8(x2p2p3A17+(p2(p3Ak+(x2p2p3A спрощується таким чином
A8=p3(x2p2A17+(x2p2Ak)+(p3(p2Ak=p3p2(x2A17+(x2Ak)+(p3(p2Ak=
1 Xj 0
Pi 0
1
Мал.1.6 Приклад чекаючо( вершини Pi
=[(p3p2(x2A17+(x2Ak)]+p3p2(x2A17+(x2Ak)+(p3(p2Ak+[p3(p2Ak]=(p2Ak+p2(x2A17+(
x2Ak). Тут вершина А8 не зустр(ча(ться у ГСА ,в кодах яких присутн(
комб(нац(( (p3p2 ( p3(p2. Нижче наведено розклад ус(х неелементарних
формул переходу.
A0=p1((p2(p3A1)+(p1((x1(p2(p3A1+(p2p3A1+x1(x2(p2(p3A2+x1x2(p2(p3A3+
+(x1p2p3A8+x1p2p3A13+p2(p3A14)=p1((p2(p3A1)+[p1(p2(p3A1]+
+(p1(p2((x1p3A8+x1p3A13+(p3A14)+(p2((x1(p3A1+p3A1+x1(x2(p3A2+
+x1x2(p3A3))=p1((p2A1)+[p1p2A1]+(p1(p2(p3((x1A8+x1A13)+(p3A14)+
+(p2((p3((x1A1+x1x2A3+x1(x2A2)+p3A1))= p1A1+(p1(p2(p3( (x1A8+
+x1A13)+(p3A14)+(p2((p3((x1A1+x1(x2A3+(x2A2))+p3A1))
A1=(p1(p3A7+(p3A2)+p1(p3A6+[p1p3A6]= (p1(p3A7+(p3A2)+p1A6
A2=p1((p2p3A21)+(p1((p2(p3A6+p2p3A18)= p1((p2p3A21)+[p1(p2p3A21]+
+(p1((p2(p3A6+[p2(p3A6]+p2p3A18+[p3(p2A18])=p1((p2A21)+(p1((p3A6+
+p3A18)=p1((p2A21)+[p1p2A21]+(p1((p3A6+p3A18)=p1A21+(p1((p3A6+
+p3A18)
A6=p1((p2(p3A19)+[p1(p2p3A19]+(p1(p2p3A2+(p2(p3A7+(p2p3A12+p2(p3Ak)=
=p1(p2A19+[p1p2A19]+(p1(p2(p3A2+(p3Ak)+(p2((p3A7+p3A12))=p1A19+
+(p1(p2(p3A2+(p3Ak)+(p2((p3A7+p3A12))
A7=p3(x3A6+(x3A9)+(p3A8
A8=p3(x2p2A17+(x2p2Ak)+(p3(p2Ak=p3p2(x2A17+(x2Ak)+(p3(p2Ak=
=[(p3p2(x2A17+(x2Ak)]+p3p2(x2A17+(x2Ak)+(p3(p2Ak+[p3(p2Ak]=(p2Ak+
+p2(x2A17+(x2Ak)
A12=(p2p3A22+p2(p3A13+[p2p3A22]+[(p2(p3A13]=p3A22+(p3A13
A17=p1(p2(p3A2+[p1(p2p3A2]+(p1p2p3A6+[(p1(p2p3A6]=p1(p2A2+[p1p2A2]+
+(p1p3A6+[(p1(p3A6]=p1A2+(p1A6
A19=x1((x2A2+x2A20)+(x1A21
Об'єднану ГСА Г0 (мал.1.7) побудуємо відповідно до формул переходу,
замінюючи кожну мітку Аi відповідною операторною вершиною Yt, а кожний
вираз Xi і Pj відповідними умовними вершинами.
-----------------------
Y1
Y10
Y8
Y9
Y11
Y5
Y8
Y9
Y1
Y8
Y5
Y2
Y13
Y17
Y8
Y3
Y14
Y15
Y7
Y16
Y17
Y18
Y5
Y18
Y2
Y9
Y20
Y5
Y10
Y9
Y1
Y5
Y12
Y1
Y20
Y10
Y12
A
B