Например.

Дан фрагмент ГСА (рис.2а). Запишем формулу перехода Y₄®U b_4sּY_s:

Y₄ ® X₂ ØX₁ Y₅ Ú X₂ X₁ Y₁ Ú ØX₂ X₁ Y₁ Ú ØX₂ ØX₁ Y₇.

Данному фрагменту ГСА соответствует следующее разложение формулы перехода по переменным X₁ и X₂. Разложим исходную формулу по переменной X₂:

Y₄®X₂(X₁Y₁ÚØX₁Y₅)ÚØX₂(X₁Y₁ÚØX₁Y₇).

Разложим исходную формулу по переменной X₁:

Y₄®X₁(X₂Y₁ÚØX₂Y₁)ÚØX₁(X₂Y₅ÚØX₂Y₇)®

® X₁Y₁ØX₁(X₂Y₅ÚØX₂Y₇).

Этому разложению соответствует фрагмент ГСА, приведенный на рис.2б.

Объединение ГСА с помощью МСА

В объединяемых ГСА должны встречаться одинаковые операторные и условные вершины (одинаково обозначенные и имеющие одинаковый смысл: в одинаково обозначенных вершинах должны быть одинаковые буквы алфавитов W и Z).

Для объединяемых ГСА строятся МСА, затем строится и заполняется объединённая МСА, записываются формулы переходов и после их разложения по переменным X_sj строятся фрагменты объединённой ГСА, которые затем объединяются путем совмещения операторных вершин. При записи объединённой МСА вводятся дополнительные логические условия (вершины), обеспечивающие заданный алгоритм работы автомата.

Например, даны две ГСА: Г1 (рис.3а) и Г2 (рис.3б). В этих ГСА встречаются одинаковые операторные и условные вершины. Составим для Г1 матрицу МСА1, а для Г2 матрицу МСА2.

Так как объединяются всего две ГСА, то введём одну дополнительную переменную (логическое условие) P. Условие Р будет определять, по какому пути будут идти переходы в объединенной ГСА в зависимости от того, какой алгоритм реализуется в настоящий момент.

Пусть для Г1 условие P = 1, а для Г2 - P = 0.

МСА1

Построим объединённую МСА используя условие Р, если выполняется алгоритм по ГСА Г1 и условие ØP, если выполняется алгоритм по ГСА Г2 .

МСА2

МСА -объединенная

Запишем формулы переходов по объединенной МСА:

Y₁® (PÚØP)Y₃ ®Y₃

Y₂® (PÚØP)Y₃ ®Y₃

Y₃® (PÚØP)Y_k ®Y_k

Y₄® ØPY₃ ®Y₃, т. к. в строке Y₄ нет P, а значит в Г1 нет вершины Y₄ , и условие ØР из формулы можно исключить.

Y_н® (PÚØP)ØX₁Y_н Ú (PÚØP)X₁X₂Y₁ Ú PX₁ØX₂Y₂ ÚØ PX₁ØX₂X₃Y₂ Ú

Ú ØPX₁ØX₂ØX₃Y₄ ®

® ØX₁Y_н Ú X₁X₂Y₁ Ú PX₁ØX₂Y₂ Ú ØPX₁ØX₂X₃Y₂ Ú ØPX₁ØX₂ØX₃Y₄

Формулы Y₁ – Y₄ – простые, их не надо разлагать. Разложение Y_н удобно начинать с переменной, чаще всего встречающейся в формуле. Это переменная X₁ :

Y_н ® ØX₁(Y_н) Ú X₁(X₂Y₁ Ú PØX₂Y₂ Ú Ø PØX₂X₃Y₂Ú ØPØX₂ØX₃Y₄);

Далее разложим формулу по X₂ :

Y_н ® ØX₁(Y_н) Ú X₁(X₂(Y₁) Ú ØX₂(PY₂ ÚØ PX₃Y₂ Ú ØPØX₃Y₄));

Далее разложим формулу по X₃. Так как в последнем разложении в выражении PY₂ не содержится переменной X₃, преобразуем его следующим образом: PY₂ = PY₂ (X₃ÚØX₃) и получим:

Y_н ® ØX₁(Y_н) Ú X₁(X₂(Y₁) Ú ØX₂(X₃(PY₂ÚØPY₂) ÚØX₃(PY₂ Ú ØPY₄))) ® ®ØX₁(Y_н) Ú X₁(X₂(Y₁) Ú ØX₂(X₃(Y₂) ÚØX₃(PY₂ Ú ØPY₄)))..

По полученным объединенным формулам переходов построим фрагменты объединенной ГСА (Рис.4а):

Объединим фрагменты ГСА, учитывая, что не может быть двух операторных вершин одного вида (Рис. 4б). Вид объединённой ГСА зависит от вида фрагментов (подграфов), которые, в свою очередь, зависят от порядка разложения формул перехода.