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

При определении основной модели с конечным числом состояний (см. § 1.6) молчаливо предполагалось, что характеристические функции f_z и f_s конечного автомата определены для каждой пары (x_v, s_v). При изучении автоматов с ограничениями на входе удобно видоизменить эту модель и допустить наличие пар (x_v, s_v), для которых обе функции f_z и f_s остаются неопределенными. В частности, мы можем предполагать, что f_z и f_s у автомата не определены для пары (ξ_j, σ_i), где ξ_j — входной символ, a σ_i — состояние автомата М, если ни при каких условиях ξ_j не может быть приложен к М| σ_i, при этом говорят, что автомат М имеет ограничение на входе в состоянии σ_i. В таблице переходов автомата М такое ограничение отмечается тем, что клетки в обеих подтаблицах z_v и s_v+1, расположенные на пересечении строки l и столбца ξ_j, остаются пустыми (или заполняются прочерками). Входная последовательность называется допустимой в состоянии σ_i, если при приложении к M| σ_i она не нарушает ограничения на входе ни в каком состоянии автомата М. В качестве примера на рис. 7.1 и в таблице 7.1 представлен автомат A32 с ограничениями на входе.

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

последовательность. Состояния σ_i и σ_j несовместимы, если существует, по крайней мере, одна входная последовательность, допустимая как для σ_i, так и для σ_j, при подаче которой на M| σ_i и M| σ_j автомат выдает различные выходные последовательности. Видно, что совместимость обладает

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

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

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

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

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

Например, таблица 7.2 представляет конечный вариант таблицы пар для автомата A32, изображенного на рис. 7.1. Из таблицы следует, что совместимыми парами в автомате A32 являются: {1,2}, {1,3}, {1,5}. {2,3}, {2,4}, {2,5}, {3,5}. {3,6} и {4.6}.