Математический аппарат инженера

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

Например, таблица для неполного автомата, граф которой изображен на рис. 241, a, имеет следующий вид:

- 577 -

Здесь вход 0 в состояниях 1 и 5, а также вход 1 в состояниях 0 и 5 являются запрещенными. Кроме того, в состоянии 3 при воздействии 0 и в состоянии 4 при воздействии 1 выходы не определены.

Входная последовательность называется допустимой для автомата в состоянии s_i, если она не нарушает ограничений на входе ни в каком состоянии автомата М и порождаемый ею выход определен на заключительном такте. На других тактах входной последовательности выходы могут быть и не определены, но последовательность состояний обязательно должна существовать. Например, для приведенного автомата в состоянии 0 допустимая входная последовательность {0, 1,0} порождает последовательность состояний {1, 4, 5} и заключительный выход 0. В то жевремя последовательность {0, 1, 1} не допустима, так как заключительный выход не определен.

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

Сокращенная форма неполного автомата М – это такой автомат М', который по отношению к допустимым для М входным последовательностям ведет себя на выходах так же, как и исходный автомат М, но имеет меньшее число состояний. Автомат М' квазиэквивалентен автомату М. Отношениеквазиэквивалентности рефлексивно и транзитивно, но не симметрично, т. е обладает всеми свойствами отношения включения. Поэтому говорят также, что М' включает М и записывают М ⊂М'. При этом из М ⊂М' вовсе не следует М' ⊂М, что иногда выражают словами: М' делает столько же и, быть может, больше, чем М.

10. Минимизация неполных автоматов. Эта задача сводится к поиску квазиэквивалентного автомата, который имеет наименьшее число состояний, и решается следующим образом.

Сначала на множестве состояний 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 не входят в один и тот же класс толерантности и, следовательно, они несовместимы.

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