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

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.

0 X1 1.

A1.

4 X2.

A2 1.

A3.

A4.

A5.

A6.

A7.

A8.

К (НЕЦь Ak.

Мал.1.1. Часткова граф-схема алгоритму Г1.

ПОЧАТОК A0.

A1.

A7.

0 3 1.

X3.

4 5.

A9 A6.

6 7.

A10 A12.

8 9.

A3 A22.

A11.

К (НЕЦЬ Ak.

Мал.1.2. Часткова граф-схема алгоритму Г2.

ПОЧАТОК A0.

A11.

0 2 1.

X1.

3 4.

A15 A16.

5 1.

X3 A12.

7 8.

A6 A13.

К (НЕЦЬ Аk.

Мал.1.3. Часткова граф-схема алгоритму Г3.

ПОЧАТОК A0.

0 1.

X1.

A13.

A9.

A8.

1 X2.

6 0.

A17.

A6.

A2.

A18.

К (НЕЦЬ Ak.

Мал.1.4. Часткова граф-схема алгоритму Г4.

ПОЧАТОК A0.

A1.

A6.

A19.

0 1.

X1.

0 X2.

A20.

A17.

A2.

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.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.