Свойства совместимости состояний

Два состояния автомата s_m и s_n называются совместимыми, что обозначим как s_m ~ s_n, если при подаче произвольного входного сигнала x_i из входного алфавита Х на вход автомата, который находится в состоянии s_m, и этого же сигнала x_i, когда автомат находится в состоянии s_n, на выходе формируется непротиворечивый выходной сигнал y_i. То есть при различных состояниях, в которых находится цифровой автомат, входные и выходные сигналы определены и совпадают. Совместимость состояний иллюстрируется на рисунке 1.

Рисунок 1 Совместимость состояний

Состояния автомата S_m и S_n совместимы при условии воздействия на вход цифрового автомата одного и того же входного сигналы x_i и при этом на выходе на выходе будет формироваться одинаковый сигнал y_i.

Свойства совместимости состояний.

1. s_m ~ s_n - рефлексивность;

2. s_m ~ s_n => s_n ~ s_m - симметричность. Если состояние s_m совместимо с состоянием s_n. следовательно, состояние s_n совместимо с состоянием s_m;

3. s_m ~ s_к & s_n ~ s_к Þ s_m ~ s_n - нет транзитивности. Если состояние s_m совместимо с состоянием s_к. и состояние s_n совместимо с состоянием s_к,

следовательно, состояние s_m совместимо с состоянием s_n.

Два состояния s_m и s_n совместимы, если для любого x_i Î X, где функции определены, выполняются два условия:

· функции переходов совместимы d(s_m, x_i) ~ d(s_n, x_i) - условие совместимости по переходу. Это означает что при воздействии на вход автомата входного сигналы x_i, находящегося в состояниях s_m и s_n, он переходит в одно и тоже состояние s_к, либо в совместимые состояния.

· функции выходов равны l(s_m, x_i) = l(s_n, x_i) - условие совместимости по выходу. Это означает что при воздействии на вход автомата входного сигналы x_i, находящегося в состояниях s_m и s_n, на выходе будет формироваться один и тот же сигнал y_i.

Классом совместимости состояний C называют множество состояний, все элементы которого попарно совместимы друг с другом.

Пример: состояния s_1, s_3, s₅ по приведенному признаку совместимы, следовательно, они принадлежат одному классу совместимости С = {s_1, s_3, s₅}.

Классы совместимости могут пересекаться.

Класс совместимости максимален, если он не содержится полностью в другом классе.

Пример. Рассмотрим отношения классов совместимости С₁ = {s_1, s_3, s₅}, С₂ = {s_2, s_3, s₅, s_7, s_9, } и С₃ = {s_3, s_7, s₉}. Класс С₁ = {s_1, s_3, s₅} является максимальным по отношению к классу С₂ = {s_2, s_3, s₅, s_7, s₉} так как он полностью не содержится в классе С₂ (в классе С₂ отсутствует состояние s₁). В свою очередь класс С₂ по отношению к классу С₁ также является максимальным на основании выше приведенных условий (в С₁ отсутствуют состояния s_2, s_7, s₉). В тоже время класс совместимости С₃ = {s_3, s_7, s₉} не является по отношению к классу С₂ максимальным, так как полностью содержится в нём.