Декомпозиция автомата при наличии СП-разбиения
Разбиение p(S) = {p1(S), p2(S), ¼, pk(S)} называется СП-разбиением (разбиением со свойством подстановки), если из того, что si и sj находятся в одном блоке, следует, что при одинаковом входном слове x состояния в которые перейдет автомат (d(si, x) и d(sj, x)) также будут находиться в одном блоке. Если для автомата А СП-разбиение существует, то можно построить автомат А´, для которого состояниями являются имена блоков разбиения и под действием любого входного сигнала из алфавита X он переходит из блока в блок по функции автомата А. Такой автомат называют фактор - автоматом автомата А по разбиению p. В этом случае автомат можно представить последовательным соединением автомата А1 и автомата А11, состояниями которого являются блоки разбиения, ортогонального с СП-разбиением. Методику определения СП-разбиений рассмотрим на примере автомата, заданного таблицей переходов и выходов (табл. 22). Таблица 22
Шаг1. Предположим, что состояния s1 и s2 принадлежат одному блоку {1, 2}. По сигналу x 1 автомат переходит в состояния s4 и s1 {4, 1}, а по сигналу x 2 в состояния s5 и s3 {5, 3}. Если хотя бы одно из состояний в разных блоках совпадает, то эти блоки объединяются. Блоки {1, 2} и {4, 1} объединяются в один блок {1, 2, 4} так как состояние 1 принадлежит обоим блокам. В результате получаем два блока {1, 2, 4} и {5, 3}. Шаг 2. Рассмотрим переход автомата из блока {1, 2, 4}. По сигналу x 1 автомат переходит в состояния s4, s1 и s1, которые принадлежат одному блоку {1, 2, 4}. По сигналу x 2 автомат переходит в состояния s5, s3 и s2, которые объединяются в один блок {5, 3, 2}. Так как блоки {1, 2, 4} и {5, 3} имеют общие состояния с блоком {5, 3, 2}, то все блоки объединяются в один блок {1, 2, 3, 4, 5}. Шаг 3. Рассмотрим переход автомата из блока {1, 2, 3, 4, 5}. По сигналу x 1 автомат переходит в состояния s4, s1 и s3, которые принадлежат одному блоку {1, 2, 3, 4, 5}. По сигналу x 2 автомат переходит в состояния s5, s3, s6, s2 и s4, которые объединяются в один блок {5, 3, 6, 2, 4}. Так как блоки {1, 2, 3, 4, 5} и {5, 3, 6, 2, 4} имеют общие состояния, они объединяются в один блок {12, 3, 4, 5, 6}. Не трудно видеть, что при предположении о том, что состояния s1 и s2 принадлежат одному блоку, все состояния входят в один блок. Следовательно, при данном предположении СП-разбиение отсутствует, и состояния s1 и s2 не должны входить в один блок. Далее последовательно рассматриваем предположения о том, что состояния (s1 и s3), (s1 и s4), (s1 и s5) и т.д. принадлежат одному блоку. Попарно рассматриваются все состояния цифрового автомата. Рассмотрим предположение о том, что состояния s1 и s3 принадлежат одному блоку {1, 3}. Шаг1. По сигналу x 1 автомат переходит в состояние s4 {4}, а по сигналу x 2 в состояния s5 и s6 {5, 6}. В результате получаем два блока {4} и {5, 6}, так как нет общих элементов. Шаг 2. Рассмотрим переход автомата из блока {4}. По сигналу x 1 автомат переходит в состояние s1 {1}, которое входит в блок {1, 3}, и по сигналу x2 в состояние s2, {2}. В результате получаем четыре независимых блока {1, 3}, {2}, {4} и {5, 6}. Шаг 3. Рассмотрим переход автомата из блока {5, 6}. По сигналу x 1 и x 2 автомат переходит в состояния s3, и s4, которые принадлежат блоку {3, 4}. Так как блоки {1, 3}, {4} и {3, 4} имеют общие состояния, то они объединяются в один блок {134}. В результате получается три блока {134}, {2}, и {56}. Шаг 4. Рассмотрим переход автомата из блока {1, 3, 4}. По сигналу x 1 автомат переходит в состояние s4 и s1{1, 4}, а по сигналу x 2 в состояния s5, s6 и s2 {5, 6, 2}. Блок {1, 4} входит в состав блока {1, 3, 4}, а блоки {5, 6}, {2} и {5, 6, 2} объединяются в один. В результате получаем два блока {1, 3, 4} и {2, 5, 6}. Шаг 5. Рассмотрим переход автомата из блока {2, 5, 6}. По сигналу x 1 автомат переходит в состояние s1, s3 и s4 {1, 3, 4}, а по сигналу x 2 в состояния s3, s4 и s3 {3, 4}, входящий в блок {1, 3, 4}. Анализируя шаги 4 и 5 нетрудно видеть, что исходный автомат имеет СП-разбиение в виде двух блоков p(S1) = {1, 3, 4}, {2, 5, 6}. Это обусловлено тем, что при одинаковых входных сигналах, автомат, находясь в состояниях, принадлежащих одному блоку, переходит в состояния, также принадлежащие одному блоку. При рассмотрении не важно, в каком блоке находятся исходные состояния и в каком блоке находятся состояния, в которые переходит автомат при воздействии входного сигнала. Главное, чтобы они принадлежали одному блоку. Обозначим блок {1, 3, 4} как b1 и блок {2, 5, 6} как b2. Тогда фактор-автомат А1 по этому разбиению будет иметь два состояния. Составим таблицу переходов для фактор - автомата А1, которая будет иметь три строки и три столбца. Рассматриваем состояние b1 {1, 3, 4}. По сигналу x 1 автомат переходит в состояние b1 {1, 3, 4}, а по сигналу x 2 в состояние b2 {2, 5, 6}. При рассмотрении состояния b2 {2, 5, 6}, видно, что по сигналам x 1 и x 2 автомат переходит в состояние b1 {1, 3, 4}. Таблица переходов для фактор - автомата А1 имеет вид таблицы 23. Таблица 23
Выберем в качестве разбиения, ортогонального с СП-разбиением, разбиение p(S) ={15, 23, 46}. Обозначим его блоки как с1 = {1, 5}, с2 = {2, 3} и c3 = {4, 6} и примем их за состояния второго автомата А11. Тогда исходному автомату будет сопоставлено последовательное соединение автомата А1, на вход которого поступают переменные множества входных сигналов X, и автомата А11, на вход которого поступают переменные множества входных сигналов X и выходные сигналы автомата А1. Схема соединения автоматов представлена на рисунке 5.
Рисунок 5 Соединение автоматов Описание автомата А11 легко получить, если учесть, что состояниям исходного автомата сопоставлены состояния автоматов А1 и А11. Составим таблицу переходов для автомата А11 при условии, что совокупность состояний автоматов А1 и А11 определяется «одним» состоянием исходного автомата на множестве состояний S = {1, 2, 3, 4, 5, 6}. Для определения состояния исходного автомата необходимо получить произведение состояний автоматов А1 и А11 (p(А1) х p(А11) или {1, 3, 4}, {2, 5, 6} х х {1, 5}, {3, 2}, {4, 6}), при условии, что эти состояния не пустые множества. Произведение состояний автоматов А1 и А11 представим в виде таблицы 24. Таблица 24
Например, если состояние автомата А1 – b1 и автомата А11 – с1, то это соответствует состоянию s1 исходного автомата ({1, 3, 4} х {1, 5} = {1}). Составим таблицу переходов автомата А11, которая будет состоять из пяти строк и четырех столбцов. Столбцы определяются состояниями автомата А11, а строки входными сигналами. Входными сигналами автомата А11 являются выходные сигналы автомата А1 и входные сигналы исходного автомата х (см. рис. 5). Таблица переходов автомата А11 представлена табл. 25.
Таблица 25
Заполняется табл. 25 на основании произведения множеств, описывающих состояния автоматов А1 и А11 (табл. 24) и таблицы переходов и выходов исходного автомата (см. табл. 22). Если автомат А1 находится в состоянии b1 {1, 3, 4}, а автомат А11 в состоянии с1 {1, 5}, то согласно табл. 24 это соответствует состоянию s1 исходного автомата. В соответствии с таблицей переходов и выходов исходного автомата (табл. 22) по входному сигналу x 1 исходный автомат должен перейти в состояние s4, что соответствует состоянию с3 {4, 6}автомата А11. Следовательно, в табл. 25 в ячейке на пересечении строки x 1/ b1 и столбца с1, должно стоять состояние с3. По входному сигналу x 2 исходный автомат должен перейти в состояние s5, что соответствует состоянию с1 {1, 5} автомата А11. В табл. 25 в ячейке на пересечении строки x 2/ b1 и столбца с1, должно стоять состояние с1. Если автомат А1 находится в состоянии b2 {2, 5, 6}, а автомат А11 в состоянии с1 {1, 5}, то согласно табл. 24 это соответствует состоянию s5 исходного автомата. В соответствии с таблицей перехода и выходов исходного автомата (табл. 22) по входному сигналу x 2 исходный автомат должен перейти из состояния s5 в состояние s3, что соответствует состоянию с2 {2, 3} автомата А11. Следовательно, в табл.25 в ячейке на пересечении строки x 1/ b2 и столбца с1, должно стоять состояние с2. По входному сигналу x 2 исходный автомат должен перейти из состояния s5 в состояние s4, что соответствует состоянию с3 {4, 6} автомата А11. В табл. 25 в ячейке на пересечении строки x 2/ b2 и столбца с1, должно стоять состояние с3. По вышеприведенной методике заполняются столбцы таблицы переходов автомата А11 для состояний с2 и с3. Составим таблицу выходов автомата А11, которая будет состоять из пяти строк и четырех столбцов. Столбцы определяются состояниями автомата А11, а строки входными сигналами х. Выходными сигналами автомата А11 являются выходные сигналы автомата А (см. рис. 5). Таблица выходов автомата А11 представлена табл. 26. Таблица 26
Заполняется табл. 26 на основании произведения множеств, описывающих состояния автоматов А1 и А11 (табл. 24) и таблицы переходов и выходов исходного автомата (табл. 22). Если автомат А1 находится в состоянии b1 {1, 3, 4}, а автомат А11 в состоянии с1 {15}, то согласно табл. 24 это соответствует состоянию s1 исходного автомата. В соответствии с таблицей перехода и выходов исходного автомата А (табл. 22) по входному сигналу x 1 на выходе исходного автомата будет сигнал y1. Следовательно, в табл. 26 в ячейке на пересечении строки x 1/ b1 и столбца с1, должен стоять выходной сигнал y1. По входному сигналу x 2 на выходе исходного автомата будет сигнал y2 следовательно в ячейке на пересечении строки x 2/ b1 и столбца с1, должен стоять сигнал y2. Если автомат А1 находится в состоянии b2 {2.5, 6}, а автомат А11 в состоянии с1 {1, 5}, то согласно табл. 24 это соответствует состоянию s5 исходного автомата. В соответствии с таблицей перехода и выходов исходного автомата (табл. 22) по входному сигналу x 1 на выходе исходного автомата будет сигнал y1. Следовательно, в табл. 26 в ячейке на пересечении строки x 1/ b2 и столбца с1, должен стоять выходной сигнал y1. По входному сигналу x 2 на выходе исходного автомата будет сигнал y2 следовательно в ячейке на пересечении строки x 2/ b2 и столбца с1, должен стоять сигнал y2. По вышеизложенной методике заполняются столбцы таблицы выходов автомата А11 для состояний с2 и с3. Если для автомата находится СП-разбиение, то это может существенно упростить сеть автоматов, получающуюся в результате декомпозиции.
|
