Диаграмма переходов (ДП). Конфликтная ситуация. Полумодулярная ДП

Диаграмма переходов (ДП) – это АП, ситуации которого представлены в виде булевых векторов одной и той же размерности n. Так же будем именовать и граф такого АП.

k-я компонента ситуации s_i называется возбужденной, если s_i F s_j при некотором F и k-е компоненты ситуаций s_i и s_j различны, в противном случае компонента называется устойчивой. Возбужденные компоненты помечаются символом «*».

Функционирование ДП состоит в переходе компонент из возбужденного состояния в устойчивое в результате смены ситуаций.

Ситуацию s_i диаграммы переходов (ДП) будем называть конфликтной, если существуют компонента s_ik и ситуация s_j такие, что:

1) компонента s_ik помечена символом «*»;

2) s_i F s_j, причем s_ik =s_jk;

3) компонента s_jk символом «*» не помечена.

Примеры конфликтных ситуаций: 0*0 1 *01* → 10 1 00, 0*0 0 *01* → 10 0 00

Полумодулярной ДП называют ДП без конфликтных ситуаций.

Полумодулярная ДП

Редукция диаграммы переходов.

Редукцию ДП можно осуществить по множеству ситуаций, порожденному теми или иными компонентами ситуаций.

В этом случае сначала из всего множества ситуаций S оставляют те, входные компоненты которых попали в выделенное множество значений входной компоненты X*. Таким образом, получаем множество ситуаций S*. Далее редукция строится по полученному множеству ситуаций S*.

Пример (из тетради, вроде как с практики):

Первые два элемента вектора полного состояния выберем в качестве входных компонент, последние два – в качестве выходных компонент. Определим редукцию ДП по множеству Х*={01, 10} входных компонент.

Результат редукции (б) для ДП (а) по множеству X* = {01, 10} входных компонент

Основная идея теории комплектов, сравнение с теорией множеств. Свойства комплектов.

Свойства комплектов

Операции над комплектами. Пространство комплектов

Пространство комплектов

Поиск по сайту: