МЧС России. Составление таблиц переходов и выходов минимизированного автомата

Составление таблиц переходов и выходов минимизированного автомата.

Определение максимальных классов совместимости.

Рассмотрим способ нахождения максимальных классов совместимости из совместимых пар состояний.

Алгоритм нахождения всех максимальных классов совместимости основан на результирующей таблицы совместимых состояний Ангера-Полла (табл. 1).

Таблица 1

s2	2.3
s3	2.3 2.5Х	4.5
s4	2.3	1.5Х	1.4
s5	1.3Х	Х	V	1.2
	s1	s2	s3	s4

Начинаем составление списка Ф классов совместимости с совместимых пар в крайнем правом столбце таблицы 1, имеющем, по крайней мере, одну клетку без крестов. Если в последнем столбце состояния не совместимы, переходим к предыдущему столбцу.

Рассмотрим последний столбец таблицы 1 (состояние s₄). Состояние s₄ совместимо с состоянием s₅. Отсюда, первым множеством совместимых состоянием Ф₁ будет

Ф₁ = {{4, 5}}.

Продвигаясь влево, записываем для каждого n-го столбца множество состояний в столбце S_i совместимых с рассматриваемым состоянием s_i, (S_i ~ s_i), т.е. множество всех состояний, соответствующих клеткам без крестов в n-м столбце таблицы и сравниваем их попарно с полученным списком максимальных множеств состояний.

Рассматривая столбец слева от последнего (состояние s₃) видим, что в этом столбце две пары совместимых состояния s₃ и s₅, (абсолютно совместимые) а также s₃ и s₅. На основании свойства отсутствия транзитивности следует что если

s₄ ~ s₃ & s₃ ~ s₅ Þ s₄ ~ s₅.

В нашем примере {3}~{4,5} (в третьем столбце таблицы нет крестов в строках 4 и 5).

Каждое множество S_i ({3} и {4,5}) пересекаем с каждым членом текущего списка Ф₁. В рассматриваемом примере при рассмотрении пересечения множество {4, 5} и список Ф₁ содержит единственный элемент {4, 5}:

{4,5}~{4,5} = {4,5}.

Если пересечение содержит более одного состояния, то добавляем в список состояние {3} с результатом пересечения:

{3}~{4,5} = {3,4,5}.

Следовательно новый список Ф₂ будет включать в себя два множества совместимых состояний

Ф₂= {{4,5},{3,4,5}}.

Далее проводится минимизация полученного множества Ф₂ - устранение всех повторений множеств в текущем списке и удаление всех множеств, содержащихся в других множествах списка. Не трудно видеть, что множество {4,5} полностью входит в множество {3,4,5}, которое является максимальным классом совместимости, и поглощается ею.

Следовательно, совместимыми будут состояния s₃, и s₄, s₅, ({3}~{4,5}), а результирующий список классов совместимости будет иметь вид

Ф₂ = {{3, 4, 5}}.

Далее рассматриваем столбец состояния (s₂). В нем только одна пара совместимых состояния s₂ и s₃. Следовательно, его список будет иметь вид

Ф₃ = {{2, 3}}.

Сравниваем его с предыдущим списком. Нетрудно видеть, что по отношению друг к другу они будут относиться к максимальным классам совместимости, т. к. во втором списке Ф₂ классов совместимости отсутствует состояние s₂.

Отсюда новым списком максимальных классов совместимости будет

Ф₄ = {{3, 4, 5}, {2, 3}}.

При рассмотрении столбца состояния s₁ каждые совместимые состояния {1}~{2,4} сравниваем с полученным списком. После сравнения видно, что оба множества по отношению к списку Ф₄ являются максимальными. Следовательно разобьем их на множества попарно совместимых состояния {1,2} и {1,4}. Списки совместимых состояний s₁ и s₄, а также s₁ и s₂ по отношению к предыдущему списку будут максимальны.

Новым списком максимальных классов совместимости будет множество

Ф = {{3,4,5},{2,3},{1,2},{1,4}}.

Приведём полностью результат применения второго шага ко всем столбцам:

Ф = {{4,5}};

{3}~{4,5}, Ф = {{3,4,5}};

{2}~{3}, Ф = {{3,4,5},{2,3}};

{1}~{2,4}, Ф = {{3,4,5},{2,3},{1,2},{1,4}}.

Очевидно, что результирующий список Ф является списком всех максимальных классов совместимости. Таким образом, для автомата, рассмотренного нами, множество всех классов совместимости будет иметь вид

Ф = {{3,4,5},{2,3},{1,2},{1,4}}.

Второй этап - нахождение минимального замкнутого покрытия - достаточно сложная задача, связана с перебором возможных замкнутых покрытий и здесь не рассматривается. Подробное описание алгоритма можно найти в книге С.И.Баранова "Синтез микропрограммных автоматов".

Мы же в качестве исходного замкнутого покрытия возьмем множество максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}}.

Третий этап. Процедура получения нового минимального эквивалентного автомата А' = (S', X', Y', d', l'), представляемого найденным для исходного автомата А замкнутым покрытием Ф, достаточно проста. Каждому классу совместимости C_iÎФ ставится в соответствие состояние s_i' нового автомата S'.

Для каждого класса совместимости C_i Î Ф и каждого входного сигнала x_i Î X вычисляется множество следующих за классом совместимости С_i состояния минимального автомата b_i = d(c_i,x_i).

Применим эту процедуру к нашему примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости Ф={{1,2},{1,4},{2,3},{3,4,5}}.

Поставим ему в соответствие множество состояний нового автомата S' ={b₁, b₂, b₃, b₄}. Классу совместимости {1,2} ставим в соответствие состояние b₁ нового автомата, классу совместимости {1,4} состояние b₂, классу совместимости {2,3} состояние b₃ и классу совместимости {3,4,5} состояние b₄.

По таблице переходов исходного автомата (см. табл. 1) составляем таблицу перехода

минимизированного автомата.

За классом совместимости {1,2} множества Ф, что является состоянием b₁ минимального автомата (столбцы s₁ и s₂) по входу x₁ следует класс совместимости {2,3} множества Ф, что является состоянием b₃ минимального автомата, по входу x₂ – состояние 5, которое входит в класс совместимости {3,4,5}, и является состоянием b₄ минимального автомата, по x₃ - класс совместимости {2,3}, что является состоянием b₃ минимального автомата и по входному сигналу x₄ - состояние {2}, относящееся к классу совместимости {1,2} и является состоянием b₁ минимального автомата (b₁ – так как он стоит первым во множестве Ф).

Следовательно, в минимизированном автомате, получающимся в результате совмещения состояний {1,2}, должны быть совместимы состояния {1,2}, {2,3}, {5}, {2,3}, {2}, что в нашем случае верно, так как они входят в классы совместимых состояний.

Аналогично проверив все классы совместимости, следует утверждать, что полученный автомат минимален и эквивалентен.

Таблица № 1

d	s1	s2	s3	s4	s5
x1	s2	s3	s3	--	--
x 2	--	s5	s4	s1	--
x 3	s3	s2	--	s2	s1
x 4	s2	--	s5	--	--

В результате проведенной минимизации получаем следующие значения функций переходов и выходов минимизированного автомата:

функции переходов для состояния b₁ при воздействии входных сигналов х₁, х₂, х₃ и х₄:

d({1,2}, x₁)=s₂ и s₃ ({2,3}) – что соответствует b₃ или d'(b₁, x₁) = b₃;

d({1,2}, x₂)=s₅ ({3,4,5}) – что соответствует b₄ или d'(b₁, x₂) = b₄;

d({1,2}, x₃)=s₂ и s₃ ({2,3}) – что соответствует b₃ или d'(b₁, x₃) = b₃;

d({1,2}, x₄)=s₂ ({1,2}) – что соответствует b₁ или d'(b₁, x₄) = b₁.

Функции выходов для состояния b₁ при воздействии входных сигналов х₁, х₂, х₃ и х₄ определяются как:

l ({1,2}, x₁) = y₁и y₁– что соответствует l' (b₁, x₁) = y₁;

l ({1,2}, x₂) = y₂– что соответствует l' (b₁, x₂) = y₂;

l ({1,2}, x₃) = y₁– что соответствует l' (b₁, x₃) = y₁;

l ({1,2}, x₄) = y₁ и y₁– что соответствует l' (b₁, x₃) = y₁.

Аналогичную процедуру проводим для остальных классов совместимости.

Вычерчиваем таблицу состояний минимизированного автомата, содержащей пять строк и пять столбцов, в соответствии с количеством состояний и входных сигналов минимизированного цифрового автомата (табл. 2).

Таблица № 2

d	b 1	b 2	b 3	b 4
x1	b 3	b 1	b 3	b 3
x2	b 4	b 1	b 4	b 2
x3	b 3	b 3	b 1	b 1
x4	b 1	b 1	b 4	b 4

Рассматриваем класс совместимости {1,2} соответствующий состоянию b₁ минимизированного автомата. По входному сигналу x₁ исходный автомат переходит в состояния {2,3} (см. табл. 1). Это соответствует состоянию b₃ минимизированного автомата. В ячейке на пересечении столбца b₁ и строки x₁ таблицы переходов нового автомата (табл. 3) ставиться состояние b₃.

По входному сигналу x₂ исходный автомат переходит в состояние {5}. Это соответствует состоянию b₄ минимизированного автомата. В ячейке на пересечении столбца b₁ и строки x₂ таблицы переходов нового автомата ставиться состояние b₄.

По входному сигналу x₃ исходный автомат переходит в состояния {3,2}. Это соответствует состоянию b₃ минимизированного автомата. В ячейке на пересечении столбца b₁ и строки x₃ таблицы переходов нового автомата ставиться состояние b₃.

По входному сигналу x₄ исходный автомат переходит в состояние {2}. Это соответствует состоянию b₁ минимизированного автомата. В ячейке на пересечении столбца b₁ и строки x₄ таблицы переходов нового автомата ставиться состояние b₁.

Даеле рассматриваем класс совместимости {1,4} соответствующий состоянию b₂ минимизированного автомата.

По входному сигналу x₁ исходный автомат переходит в состояние {2}, что соответствует состоянию b₁ минимизированного автомата. В ячейке на пересечении столбца b₂ и строки x₁ таблицы переходов нового автомата ставиться состояние b₁.

По входному сигналу x₂ исходный автомат переходит в состояние {1}, что соответствует состоянию b₁ минимизированного автомата. В ячейке на пересечении столбца b₂ и строки x₂ таблицы переходов нового автомата ставиться состояние b₁.

По входному сигналу x₃ исходный автомат переходит в состояния {3,2}, что соответствует состоянию b₃ минимизированного автомата. В ячейке на пересечении столбца b₂ и строки x₃ таблицы переходов нового автомата ставиться состояние b₃.

По входному сигналу x₄ исходный автомат переходит в состояние {2}. Это соответствует состоянию b₁ минимизированного автомата. В ячейке на пересечении столбца b₂ и строки x₄ таблицы переходов нового автомата ставиться состояние b₁.

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

Таблица выходов минимизированного автомата (таблица 4) составляется аналогично таблице переходов по таблице выходов исходного автомата, представленной таблицей 3.

Таблица № 3

l	s1	s2	s3	s4	s5
x1	y1	y1	y1	--	--
x 2	y2	y2	y2	y2	--
x 3	--	y1	--	--	y2
x 4	y1	--	y1	--	--

Рассматриваем класс совместимости {1,2} соответствующий состоянию b₁ минимизированного автомата. По входному сигналу x₁ на выходе исходного автомата в этих состояниях будет сигнал y₁ (см. табл. 3). В ячейке на пересечении столбца b₁ и строки x₁ таблицы переходов нового автомата (см. табл. 4) ставиться выходной сигнал y₁.

По входному сигналу x₂ на выходе исходного автомата будет сигнал y₂. В ячейке на пересечении столбца b₁ и строки x₂ таблицы переходов нового автомата ставиться выходной сигнал y₂.

По входному сигналу x₃ на выходе исходного автомата будет сигнал y₁. В ячейке на пересечении столбца b₁ и строки x₃ таблицы переходов нового автомата ставиться выходной сигнал y₁.

По входному сигналу x₄ на выходе исходного автомата будет сигнал y₁. В ячейке на пересечении столбца b₁ и строки x₄ таблицы переходов нового автомата ставиться выходной сигнал y₁.

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

Таблица № 4

l	b 1	b 2	b 3	b 4
x1	y1	y1	y1	y1
x2	y2	y2	y2	y2
x3	y1	--	y1	y2
x4	y1	y1	y1	y1

––––––––––––––––––––––––––––––––––––––––––––––––––––––

Кафедра государственно-правовых дисциплин

^{(наименование кафедры)}

«УТВЕРЖДАЮ»

начальник кафедры государственно-правовых дисциплин

подполковник внутренней службы

Чебоксаров П.А.

”_____” _____________ 2010 года

Дата добавления: 2014-01-07