Читать «Математический аппарат инженера» онлайн - страница 70

Сначала на множестве состояний S = {σ₁, σ₂, ..., σ_r} исходного автомата определяется отношение совместимости. Состояния σ_i и σ_j называют совместимыми, если любая допустимая для этих состояний входная последовательность не порождает различных заключительных выходов при начальных состояниях σ_i и σ_j автомата. Отношение совместимости рефлексивно и симметрично, однако оно не обязательно транзитивно. Отсюда следует, что совместимость является отношением толерантности. Все совместимые между собой состояния объединяются в классы толерантности S^'₀, S^'₁, ..., S^'_w, которые образуют некоторое покрытие множества состояний

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

- 578 -

символа отсутствуют различные выходы. Клетки, соответствующие запрещенным входам для данной пары состояний, заполняются прочерком и при исключении пар, как это описано в (8), не учитываются. Так, для автомата, заданного табл. 12, имеем:

Отмеченная на первом шаге пара {0, 2} является единственной несовместимой парой в таблице, так как она не содержится ни в каких других строках. Следовательно, всенеотмеченные пары являются совместимыми. Построив матрицу толерантности для совместимых пар и переставив в ней строки и столбцы, имеем:

Отсюда выделяем кассы толерантности S^'₀= {0, 1, 4, 5}, S^'₁= {0, 3, 4, 5} S^'₂= {2, 3, 4, 5}, объединяющие совместимые между

- 579 -

собой состояния. Здесь, в частности, можно убедиться в том, что совместимость не обладает свойством транзитивности. Например, пары состояний {0, 1} и {0, 3} совместимы, но состояния 1 и 3 не входят в один и тот же класс толерантности и, следовательно, они несовместимы.

Из определения совместимости и способа получения классов толерантности следует, что при воздействии любого не запрещенного входного символа автомат из совместимых состояний переходит в одно и то же или в совместимые состояния, а выходы (если они определены) при этом будут одинаковы.

Так, в нашем примере при воздействии 0 классы S'₀ и S'₁ переходят в {1, 5}, а S'₂ – в {3, 5}; при воздействии 1 класс S'₀ переходит в {4, 5}, S'₁ – в {5} и S'₂ – в {1, 5}. Следовательно, исходный автомат можно представить квазиэквивалентным ему автоматом, в котором классам совместимости S'₁, S₂,..., S'_w соответствуют состояния σ'₀, σ'₁, ..., σ'_w . Однако такой автомат не всегда будет минимальным. Для получения минимальной формы автомата необходимо отобрать наименьшее число таких классов совместимости, которые образуют покрытие множества состояний S и в то же время включают множества состояний, следующих за состояниями каждого класса при всех незапрещенных воздействиях. Для рассматриваемого примера этим требованиям удовлетворяют классы S'₀ и S'₁, так как S'₀ ∪ S'₂ = S, и все множества последующих состояний {1, 5}, {3, 5}, {4, 5} и {5} являются подмножествами S'₀ и S'₂. Соответствующая минимальная форма показана на рис. 241, б, где состояния 0и 1 соответствуют классам S'₀ и S'₂.