Декомпозиция автоматов при отсутствии СП-разбиений
Рассмотрим метод декомпозиции на примере автомата, представленного таблицей переходов и выходов в виде табл. 27. Алфавит состояний S = {1, 2, 3, 4, 5, 6}, алфавит входов X = {x1, x2, x3, x4}, алфавит выходов Y = {y1, y2, y3}. Для заданного автомата СП-разбиения нет. Таблица 27
В табл. 27 в целях сокращения обозначений состояний автомата они обозначаются цифрами 1, 2, 3 и т.д., что соответствует s1, s2, s3 и т.д. Выберем разбиение множества состояний S: π 1(S)={1234, 56}, π 2(S)={1256, 34}, π 3(S)={135, 246}, т.е. сеть будет состоять из трёх компонентных автоматов В, С и D. Условие теоремы выполняется, π 1(S), π 2(S) и π 3(S) – ортогональны (π 1(S) x π 2(S) x π 3(S) = π 0(S)). Обозначим блоки π разбиений через состояния компонентных автоматов В, С и D: π 1(S) = {1234, 56} = {b1, b2} = B; π 2(S) = {1256, 34} = {c1, c2} = C; π 3(S) = {135, 246} = {d1, d2} = D. Выбор разбиений π 1, π 2 и π 3 определяет сложность выходной функции, а от неё – со сколькими автоматами связан компонентный автомат. Для каждого разбиения pi построим функцию перехода компонентных автоматов Fi: SxX®pi, на основе функции переходов исходного автомата d (табл. 27). Эта функция определяет реакции автоматов В, С и D на внешнее воздействие xi, при условии, что автомат А находится в состоянии k. Так, например, если автомат В (соответствующий разбиению π 1(S)) находится в состоянии b1, автомат С (соответствующий разбиению π 2(S)) – в состоянии с2, автомат D (соответствующий разбиению π 3(S)) – в состоянии d1, то исходный автомат А будет находится в состоянии 3. Это определяется произведением состояний автоматов В, С и D (b1 х с2 х d1 = {1234} х х { 34} х {135} = 3). Составим функцию состояний Fв для π 1-разбиения, соответствующему автомату В и представим её в виде табл. 28. Методика составления табл. 28 сводится к сопоставлению состояний исходного автомата А с компонентным автоматом В. При воздействии на вход исходного автомата сигнала x 1, он из состояния 1 перейдет в состояние 2 (табл. 27), которое соответствует состоя- нию b1 компонентного автомата В. В табл. 28 на пересечении строки x 1 и столбца 1 ставиться состояние b1. По этому же сигналу исходный автомат Таблица 28
из состояния 2 перейдет в состояние 5 (табл. 27), которое соответствует состоянию b2 компонентного автомата В. В табл. 27 на пересечении строки x 1 и столбца 2 ставиться состояние b2. Рассматривая переход исходного автомата А при воздействии сигнала x 1 из других состояний не трудно видеть, что из состояния 3 => 1 (b1), из 4 => 6 (b2), из 5 => 1 (b1) и из 6 => 2 (b1). Символ => обозначает переход автомата из одного состояния в другое. Далее рассматриваем входной сигнал x 2, x 3, x 4 и последовательно заполняем табл. 28. Аналогично составляем таблицу состояний для разбиения π 2 автомата С и π 3 автомата D, которые представлены таблицами 29 и 30 соответственно. Таблица 29
Таблица 30
Определим для функции состояний Fi разбиение τ i на множестве состояний S так, чтобы для любых sk и sm из множества S условие для любого x Î X функции состояний компонентного автомата были равны (Fi (x, sk) = = Fi(x, sm)) выполнялось тогда и только тогда, когда sk и sm принадлежат к одной группе разбиения τ i. Определяем τ - разбиения для разбиения π 1 компонентного автомата В в соответствии с табл.28. Поочерёдно сравниваем столбцы с состояниями исходного автомата при воздействии входных сигналов и состояния автомата В. Не трудно видеть, что полностью совпадают столбцы {1, 3, 6} и {2, 4}. Столбец {5} не совпадает ни с одним столбцом. В соответствии с требованиями к разбиению τ , для автомата В оно будет равно τ 1 = {1, 3, 6}{2, 4}{5}. В соответствии с приведенной методикой определяем разбиения τ для автоматов С и D, которые соответственно равны:
τ 2 = {1, 2, 3, 4}{5, 6}; τ 3 = {1, 4}{2, 3}{5}{6}.
Определим для функций Fi разбиения η i на множестве X так, чтобы для любых x к и x m из множества X условие, что для любого x Î X Fi(x к, a) = = Fi(x m, a) выполнялось тогда и только тогда, когда x к и x m принадлежат к одной группе разбиения η i. То есть при воздействии одного и того же входного сигнала состояния компонентного автомата совпадали. Рассмотрим строки табл. 28 для автомата В. Не трудно видеть, что совпадают строки со входными сигналами x 1 и x 4, а так же x 2 и x 3. Следовательно, для компонентного автомата В η разбиение будет равно
η 1 = {x1x4, x2x3}.
Рассматривая табл. 29 и 30 определим η разбиения для автоматов С и D, которые будут соответственно равны:
η 2 = {x1x2x3, x4}; η 3 = {x1x2, x3x4}.
Построим сеть из компонентных автоматов из условия
N = < < XN, YN, { Si }, { fi }, {ji }, g > >, (1.19)
где XN = X – множество входных сигналов; YN = Y – множество выходных сигналов; Si, fi, ji – множество состояний, входные и выходные функции компонентных автоматов В, С и D, определяющие автомат А; g – выходная функция автомата А; Xi = X´ i x X´ ´ i, если X´ i – непустое множество; Xi = X´ ´ i, при условии что X´ i – пустое множество, X´ ´ i = hi. Составляющая входного сигнала X´ i определяются по следующему правилу. Если pi х (pk х pl х …х pm) £ ti, то X´ i = (pk х pl х …х pm). В рассматриваемом примере найдём все возможные произведения пересечений p-разбиений компонентных автоматов В, С и D:
p1(S) x p2(S) = {1234, 56} х {1256, 34} = {12, 56, 34}; p1(S) x p3(S) = {1234, 56} х {135, 246} = {13, 24, 5, 6}; p2(S) x p3(S) = {1256, 34} х {135, 246} = {15, 26, 3, 4}; p1(S) x p2(S) x p3(S) = {1, 2, 3, 4, 5, 6}.
Исходя из условия построения сети, установим зависимости функции перехода автомата В от других автоматов. Для этого сравним произведения p1(S) x p2(S) = {12, 56, 34} и p1(S) x p3(S) = {13, 24, 5, 6} с разбиением τ 1 = {136}{24}{5}, которое должно быть больше произведений p - разбиений. Нетрудно видеть, что эти множества несравнимы. Сравниваем произведения p1(S) x p3(S) = {13, 24, 5, 6} c разбиением τ 1. Из сравнения видно, что блоки произведения p1(S) x p3(S) полностью входят в разбиение τ 1, следовательно, выполняется условие
τ 1 ≥ p1(S) x p3(S).
Исходя, из этого следует, что X˝ = p3(S) = {135} {246}, что соответствует состояниям компонентного автомата D: d1 = {135} и d2 = {246}. Таким образом, состояния автомата В будут зависеть от состояний компонентного автомата D. Обозначим блоки разбиение η 1 на множестве входных сигналов Х через множество U, где u1 = x 1 x 4, а u2 = x 2 x 3. Составим таблицу переходов для автомата В при условии, что на его вход поступает два сигнала множеств U и D и функция перехода будет определяться выражением
δ 1 = (B х (D х U)).
Для составления таблицы переходов автомата В рассмотрим множества: B {b1= {1234}; b2= {56}}; D {d1= {135}; d2= {246}}; U {u1= { x 1 x 4}; u2= { x 2 x 3}}.
Таблица перехода автомата В будет состоять из двух столбцов с состояниями b1 и b2 в соответствии с π 1 - разбиением и четырёх строк, определяющие входные сигналы как произведение множеств D и U (табл. 31). Таблица 31
Рассматриваем состояния автоматов B и D. Если автомат В находится в состоянии b1 {1234}, а автомат D в состоянии d1 {135}, то это соответствует состояниям 1 и 3 исходного автомата b1 х d1= {1234} х {135}={13}. При воздействии на вход блока входных сигналов u1= { x 1 x 4} исходный автомат из состояния s1 переходит в состояние s2 (табл. 27), а из состояния s3 в состояние s1. Состояния s1 и s2 соответствуют состоянию b1 автомата B. Следовательно, в ячейке, на пересечении столбца b1, и строки d1, u1 должно стоять состояние b1 автомата B. При воздействии блока u2 = { x 2 x 3} при тех же состояниях автоматов B и D, исходный автомат из состояния s1 перейдёт в состояние s6, а из состояния s3 в состояние s5. Состояния s6 и s5 принадлежат блоку b2 автомата B, которое и должно стоять в ячейке на пересечении столбца b1, и строки d1, u2. При рассмотрении состояния b1 автомата В и d2 автомата D видно, что они соответствуют состояниям 2 и 4 исходного автомата b1 х d2= = {1234} х {246} = {24}. При воздействии блока u1 { x 1 x 4} входных сигналов исходный автомат из состояния s6 переходит в состояние s5, а из состояния s4 в состояние s6, что соответствует блоку b2 {56} автомата B. При воздействии блока u2 { x 2 x 3} входных сигналов исходный автомат из состояния s2 переходит в состояние s1, а из состояния s4 в состояние s2. Состояние s1 и s2 соответствует состоянию b1 {1234} автомата В. По аналогичной методике заполняются столбец b2 таблицы переходов автомата В. По методике, аналогичной автомату В, определяем влияние автоматов В и D на автомат С. Сравниваем произведения p2(S) x p1(S) = {12, 56, 34} и p2(S) x p3(S) = {15, 26, 3, 4} с разбиением τ 2 = {1234, 56}. Нетрудно видеть, что множества p2(S) x p3(S) и τ 2 несравнимы, а множество p2(S) x p1(S) полностью входит во множество τ 2. Следовательно, выполняется условие τ 2 ≥ p2(S) x p1(S). Отсюда составляющая входного сигналы X´ 2 для автомата С соответствует π 1 = {1234}{56}, что соответствует блокам b1 = {1234} и b2 = = {56} автомата В. Следовательно, состояния автомата С будут зависеть от состояний автомата В. Составляем таблицу перехода автомата С, для этого обозначим блоки разбиения η 2 множества входных сигналов Х как v1={ х 1 х 2 х 3} и v2 = { х 4} множества V. Функция переходов d2 определиться как δ 2 = (С х (B x V)). Таблица переходов автомата С составляется на основании таблицы переходов и выходов исходного автомата (табл. 27) и представлена табл. 32. Таблица 32
Рассмотрим заполнение столбца с1 табл. 32. Если автомат С находится в состоянии с1 {1256}, а автомат В находится в состоянии b1{1234}, то это соответствует состояниям s1 и s2 исходного автомата b1 х с1= {1234} х {1256}={12}. При воздействии на вход блока v1={ х 1 х 2 х 3} исходный автомат из состояния s1 переходит в состояния s2 и s6, а из состояния s2 в состояния s1 и s5. Состояния s1, s5, s2, s6 соответствуют состоянию с1 {1256} автомата С, которое записывается на пересечении столбца с1 и строки b1, v1. При воздействии блока v2 = { х 4} исходный автомат из состояния s1 переходит в состояние s2, а из состояния s2 в состояние s5, что соответствует состоянию с1 автомата С, которое записывается на пересечении столбца с1 и строки b1, v2. При условии, что автомат С находится в состоянии с1, а автомат В в состоянии b2, то это соответствует состояниям s5 и s6 исходного автомата. При воздействии блока v1={ х 1 х 2 х 3} исходный автомат переходит из состояния s5 в состояния s1 и s2, что соответствует состоянию с1 {1256} автомата С. Это состояние записывается на пересечении столбца с1 и строки b2, v1 табл. 32. При воздействии на входе блока v2 = { х 4} при тех же состояниях автоматов В и С, исходный автомат переходит из состояния s5 в состояние s4, а из состояния s6 в состояние s3. Состояния s3 и s4 соответствует блоку с2 автомата С, которое записывается на пересечении столбца с1 и строки b2, v2. Аналогично заполняется столбец с2 таблицы перехода автомата С. Интересным будет рассмотрение комбинаций состояния с2 автомата С и состояния b2 автомата В. Данные множества состояний не пересекаются с2{34} х b2{56} = 0 (пустое множество). Следовательно, такие состояния автоматов С и В недопустимы, и на пересечении строк b2, v1 и b2, v2 и столбца с состоянием автомата С с2 ставиться символ *. Определим влияние компонентных автоматов В и С на автомат D. Для этого сравним произведения p3(S) x p1(S) = {13, 24, 5, 6} и p3(S) x p2(S) = {15, 26, 3, 4} с разбиением τ 3 = {14}{23}{5}{6}. При сравнении не трудно видеть, что ни одно из множеств π - разбиений полностью не входит в разбиение τ 3, а следовательно, они не сравнимы. Таким образом, по отдельности автоматы В и С не влияют на автомат D. Для оценки совместного влияния автоматов В и С необходимо брать произведение всех π - разбиений p3(S) x (p1(S) x p2(S)) = {135, 246} х ({1234, 56}х{1256, 34}) = = {1, 2, 3, 4, 5, 6}. Произведение всех трёх π - разбиений в полном объёме входит в разбиение τ 3, а следовательно выполняется условие τ 3 ≥ p3(S) x (p1(S) x p2(S)). Исходя из условий построения сети из компонентных автоматов, составляющая входного сигналы X´ 3 для автомата D соответствует произведению p1(S) x p2(S) = {1234, 56} х {1256, 34} = {12, 56, 34}, что соответствует не пустым элементам произведения множеств состояний автоматов В и С (В х С). Функция переходов d3 определиться как δ 3 = (С х (B x С)). Произведение p1(S) x p2(S) через состояния автоматов В и С будет иметь вид {12, 56, 34} = {b1 х с1, b2 х с1, b1 х с2}. Произведение b2 х с2 представляет собой пустое множество. Составляем таблицу перехода автомата D, для этого обозначим блоки разбиения η 3 множества входных сигналов Х как w1={ х 1 х 2} и w2 = { х 3 х 4} множества W. Функция переходов d3 определиться как δ 3 = (С х ((B x С) х W)). Составляем таблицу переходов для автомата D. Она будет содержать два столбца состояний d1 и d2 автомата D и шесть строк комбинации множества (B x С) и W (табл.33) при условии отсутствия пустых множеств. Таблица 33
Если автомат D находится в состоянии d1, а автоматы В и С в состояниях b1 и c1 соответственно, то это соответствует состоянию s1 исходного автомата А, определяемое как произведение множеств d1 х b1 х c1 = {135} х {1234} х {1256} = {1}. При воздействии входного блока w1={ х 1 х 2} исходный автомат переходит из состояния s1 в состояния s2 и s6, (табл. 27), что соответствует состоянию d2 {246} автомата D, которое записывается на пересечении столбца d1 и строки b1 х с1, w1. При воздействии входного блока w2 = { х 3 х 4} исходный автомат переходит из состояния s1 в s6 и s2, что также соответствует состоянию d2 {246} автомата D и данное состояние записывается в соответствующую ячейку табл. 33. При условии нахождения автомата D в состоянии d1, а автоматов В и C в состояниях b2 и c1 соответственно, то это соответствует состоянию s1 исходного автомата. При воздействии входного блока w1={ х 1 х 2} исходный автомат А переходит из состояния s3 в состояния s1 и s5 (табл.27), что соответствует состоянию d1. При воздействии входного блока w2 = { х 3 х 4} исходный автомат переходит из состояния s3 в состояния s5 и s1, что также соответствует блоку d1 автомата D. Данные состояния записываются в соответствующих ячейках (табл. 33). По выше приведённой методике заполняются все ячейки таблицы переходов автомата D. Для определения выходного сигнала исходного автомата определяется выходная функция g, которая зависит от состояний автоматов В, С и D и множества входных сигналов исходного автомата Х. Таблица выходов автомата строится из условия комбинаций состояний всех автоматов при воздействие множества входных сигналов. Значения выходных сигналов берется из исходной таблицы переходов и выходов (табл. 26). Комбинация состояний автоматов представляет собой произведение множеств состояний автоматов В х С х D, исключая пустые множества. Данное произведение всегда равно только одному состоянию исходного автомата:
b1 х c1 х d1 = {1234} х {1256} х {135} = {1}; b1 х c1 х d2 = {1234} х {1256} х {246} = {2}; b2 х c1 х d1 = {56} х {1256} х {135} = {5}; b2 х c1 х d2 = {56} х {1256} х {246} = {6}; b1 х c2 х d1 = {1234} х {34} х {135} = {3}; b1 х c2 х d2 = {1234} х {34} х {246} = {4}.
Таблица выходов исходного автомата представлена табл. 34. Таблица 34
На основании композиции отдельных автоматов строится схема исходного автомата, которая представлена на рисунке 6.
Рисунок 6 Структурная схема соединения компонентных автоматов в сеть
|
