Операции декомпозиции

3.1.1.Разбиение. Покрытие

Разбиением заданного автомата является некоторая система автоматов, удовлетворяющая определенным требованиям.

Например, для ЦАА можно рассмотреть систему ЦАА1, ЦАА2, ... , ЦААI, ..., ЦААN. Данная система будет разбиением, если каждый автомат системы является подавтоматом ( ПЦАА ) ЦАА.

Далее, объединение автоматов системы должно совпадать с заданным автоматом. И, наконец, пересечение любой пары автоматов системы должно быть пустым.

Указанные выше три условия определения разбиения можно записать следующим образом:

1. Любой автомат системы является подавтоматом заданного автомата , то есть ЦААI < ЦАА ;

2. Объединение всех N автоматов системы совпадают с заданным автоматом, то есть:

N

U ЦААI = ЦАА ;

I=1;

3. Пересечение любой пары автоматов пусто , то есть:

ЦААI ЦААJ = ЦА0 (при I ¹ J).

Можно осуществлять разбиение автомата, если он представлен в виде совмещенной матрицы переходов и выходов автомата Мили или отмеченной матрицы переходов автомата Мура.

Ниже разбиение рассматривается для автомата Мили (табл.15).

Операцию разбиения проще выполнить на графе автомата (рис.17).

Каждый подавтомат системы характеризуется областями отправления A_i, прибытия B_i и графиком соответствия p_i, где i - номер подавтомата (рис. 18 и 19).

Процедуру разбиения ЦА можно сформулировать так:

1. Начать;

2. Выбрать стартовую вершину с наименьшим индексом, не входящую в области отправления предыдущих ПЦАА;

3. Формировать область прибытия В_i;

4. Формировать область отправления A_i;

5. Проверить, что все переходы учтены, при "нет" перейти к п.3;

6. Проверить, что остались вершины, не входящие в предыдущие области отправления, при "да" перейти к п.2;

7. Закончить.

Если все переходы для вершины рассмотрены, то над ней рекомендуется ставить "точку".

Таблица 15

Автомат для разбиения

ПС ВС	s1	s2	s3	S4	s5	s6
Х1	s1/y2	s1/y3	s2/y4	s6/y5	s6/y1	s5/y6
Х2	s2/y3	s4/y5	s3/y4	s5/y6	s6/y2	s5/y1

y4 y3 x1 x2 s2 s3 x2 y4 y2 x2 x1 s1 y5 x1 y3 x1 s4   y5 x1 y6 x2 s6 y1 x1 s5 y2 x2 y6 x2 y1 Рис.17. ГА с разбиением в первом цикле в качестве начальной вершины следует выбрать вершину с наименьшим индексом (s1). Этот цикл разбиения представлен на рис.18. Для второго цикла следует выбрать стартовую вершину с наименьшим индексом, невходящую в область отправления предыдущих циклов (в данном случае в предыдущих циклах всего один – первый цикл ). Ясно, что стартовой вершиной будет вершина s4 (рис.19). Больше вершин для старта не осталось, разбиение дало два подавтомата (выделены пунктиром на рис.17).

. .

s₁ s₁ . .

. . s₄ s₅

А₁ s₂ s₂ В₁ А₂ . . В₂

. . s₅ s₆

s₃ s₄

.

s₃

Рис. 18 Рис. 19

Легко представить СТП и В этих подавтоматов ( табл.16, 17).

Таблица 16

1-й подавтомат

ПС ВС	s1	s2	s3
X1	s1/y2	s1/y3	s4/y4
X2	s2/y3	s4/y5	s3/ y4

Таблица 17

2-й подавтомат

ПС ВС	s4	s5	s6
x1	s6/y5	S6/y1	s5/y6
x2	s5/y6	S6/y1	s5/y1

В систему ПЦАА (табл.16, 17) для ЦАА (табл.15) входит два подавтомата.

Первый подавтомат (табл.16) должен включать вершину s₁ в области отправления как стартовую (рис.18). Видно, что А₁ = (s₁, s₂, s₃), В₁ = (s₂ ,s₃, s₄).

Второй ПЦАА (табл.19) следует начать с вершины s₄. Видно, что А₂ = (s₄, s₅, s₆), B₂ = (s5, s6).

С учетом областей отправления и прибытия условия корректности разбиения можно сформулировать следующим образом:

1. Пересечения любой пары областей отправления пусто: А_i /\ А_j = 0

(i ¹ j),

2. Пересечение любой пары областей прибытия пусто: В_i /\ В_j = 0 (i ¹ j),

3. Пересечение любой пары графиков пусто: р_i /\ р_j = 0 (i ¹ j),

где знак /\ использован в качестве знака пересечения.

Если какое-либо условие не соблюдается, то где-то допущена ошибка.

Эти условия корректности являются расшифровкой ранее сформулированного 3-его условия определения разбиения.

Частным случаем разбиения является покрытие, оно отличается от разбиения третьим условием определения разбиения (покрытия):

3. Пересечение хотя бы одной пары автоматов системы не пусто (i ¹ j).

3.1.2. Проверка разбиения, покрытия

Указанные выше условия определения разбиения (покрытия) можно использовать тогда, когда предложена система, претендующая на разбиение (покрытие).

Если разбиение автомата выполнено и получены области отправления, прибытия, то пересечение любой пары подавтоматов легко проверить через пересечения областей.

Естественно, что в том случае первое из указанных выше условий определения проверять не следует, так как разбиение дает подавтоматы.

После разбиения второе условие также нет необходимости проверять, так как алгоритм разбиения гарантирует соблюдение указанного выше условия.

Операция проверки покрытия автомата отличается от операции проверки разбиения автомата по третьему условию определения. В данном случае пересечение хотя бы одной пары подавтоматов не является пустым, т.е. ЦААI /\ ЦААJ = ЦА0 при I ¹ J.

Дата добавления: 2015-07-26; просмотров: 134; Нарушение авторских прав

Мы поможем в написании ваших работ!