3.2. Эквивалентность состояний

В дальнейшем будем применять обозначение для краткой записи высказывания: «автомат М в состоянии ».

Определение 3.1. Говорят, что состояние автомата и состояние автомата эквивалентны, если под воздействием любой входной последовательности выдают одинаковые выходные последовательности. Если не эквивалентны, то говорят, что они различимы. Обозначения могут относиться к одному и тому же автомату.

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

Эквивалентность обозначается равенством а различимость — неравенством Пользуясь определением 3.1, можно легко показать, что эквивалентные состояния обладают свойством рефлексивности свойством симметричности (если то ) и свойством транзитивности (если то ). Следовательно, эквивалентность состояний может рассматриваться как обычное соотношение эквивалентности, которое применимо к множествам состояний любой мощности. Различимость состояний не обладает свойствами рефлексивности и транзитивности и, следовательно, может относиться только к парам состояний.

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

Некоторые из этих случаев описываются с помощью следующих трех лемм.

Лемма 3.1. Пусть автомата М. Если строки в подтаблице автомата М различаются, то

Доказательство. Очевидно, существует по крайней мере один входной символ, при приложении которого к на выходе М получаются различные выходные символы. Следовательно, по олределению 3.1

Лемма 3.2. Пусть состояния автомата М. Если строки в полной таблице переходов автомата М одинаковы, то

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

Лемма 3.3. Пусть и состояния автомата М. Если строки полной таблицы переходов автомата М становятся одинаковыми при замене каждого обозначения на (или наоборот), то

Доказательство. При приложении любого входного символа к выходные символы одинаковы в двух случаях: либо переходят в одно и то же состояние, либо в состояния (не обязательно соответственно). Если следующее состояние одно и то же, то реакции автомата на входные подпоследовательности будут совпадать. Если следующими состояниями являются , то восстановится исходная ситуация, и приведенные выше соображения можно будет повторить, чтобы показать, что следующие выходные символы одинаковы в обоих случаях. Затем, по индукции, получим, что реакции при на любую входную последовательность будут одинаковыми, откуда следует, что

Пары строк, обладающие свойством, приведенным в лем называются явно различимыми, а состояния, стоящие в основном столбце в этих строках, — явно разли чимыми состояниями. Пары строк, обладающие свойствами,

указанными в леммах 3.2 и 3.3, называются явно эквивалентными, а состояния, стоящие в основном столбце в этих строках,-явно эквивалентными состояниями.

Таким образом, имеем:

Теорема 3.1. Если состояния явно различимы, то а если состояния явно эквивалентны, то .

Следует отметить, что утверждение, обратное теореме 3.1, несправедливо, т. е. не каждая пара различимых состояний является явно различимой и не каждая пара эквивалентных состояний явно эквивалентной. Используя определения, введенные в § 2.3, можно заключить, что в явно минимальном автомате все пары состояний различимы, а в явно сократимом автомате имеется по крайней мере одна пара эквивалентных состояний.

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

Для иллюстрации лемм рассмотрим автомат представленный графом переходов, изображенным на рис. 3.1, и таблицей переходов 3.1.

Из таблицы переходов видно, что строки 1 и 5 одинаковы, а строки 2 и 6 становятся одинаковыми, если каждую цифру 2 заменить на цифру 6 (или каждую цифру 6 заменить на цифру 2). Следовательно, состояния в парах {1,5} И {2, 6} являются эквивалентными. Рассмотрение подтаблицы

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

лицы показывает также, что ни одно состояние из множества не может быть эквивалентным какому-либо состоянию из множества