Прикладная теория цифровых автоматов

Прикладная теория цифровых автоматов

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

К(НЕЦЬ А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- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо сл(дуючу систему формул:

+(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

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