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

При определении основной модели с конечным числом состояний (см. § 1.6) молчаливо предполагалось, что характеристические функции конечного автомата определены для каждой пары При изучении автоматов с ограничениями на входе удобно видоизменить эту модель и допустить наличие пар для которых обе функции остаются неопределенными. В частности, мы можем предполагать, что у автомата не определены для пары где — входной символ, а — состояние автомата М, если ни при каких условиях не может быть приложен к при этом говорят, что автомат М имеет ограничение на входе в состоянии таблице переходов автомата М такое ограничение отмечается тем, что клетки в обеих подтаблицах расположенные на пересечении строки I и столбца остаются пустыми (или заполняются прочерками). Входная последовательность называется допустимой в состоянии если при приложении к она не нарушает ограничения на входе ни в каком состоянии автомата М. В качестве примера на рис. 7.1 и в таблице 7.1 представлен автомат (с ограничениями на входе.

Состояния автомата М с ограничениями на входе называются совместимыми, если для при подаче на вход любой допустимой для и входной последовательности на выходе появляется одна и та же

последовательность. Состояния несовместимы, если существует, по крайней мере, одна входная последовательность, допустимая как для так и для , при подаче которой на автомат выдает различные выходные последовательности.

Рис. 7.1. Автомат .

Видно, что совместимость обладает свойствами рефлексивности и симметричности, но не обладает свойством транзитивности, так как последовательности, допустимые для не обязательно допустимы для

Таблица 7.1. Автомат

Совместимость поэтому нельзя понимать как обычное отношение эквивалентности, а следует относить только к парам состояний.

Следует заметить, что определение совместимых пар состояний совпадает с определением эквивалентных пар состояний, если на входные последовательности рассматриваемого автомата не накладываются никакие ограничения. Таким образом, определение совместимости пар состояний может быть получено из определения эквивалентности пар состояний, если в последнем (см. определение 3.1) выражение «любой входной последовательности» заменить выражением «любой входной последовательности, допустимой для обоих состояний» (это изменение не отразится на правильности определения 3.1, так как в автомате без ограничений на входе множество допустимых последовательностей составляет множество всех последовательностей). Поэтому определение пары совместимых состояний производится так же, как определение пары эквивалентных состояний, с той лишь разницей, что все последовательности, недопустимые для обоих состояний пары, не учитываются.

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

Таблица 7.2. Таблица пар для автомата

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

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