7.4. Отличимость состояний автоматов

ОПРЕДЕЛЕНИЕ

Состояния q_i и q_j автомата  называются отличимыми, если существует такое входное слово , что

( ) ( ).

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

В качестве примера рассмотрим автомат, изображенный на рис. 7.6.

0(0) 0(0)

q₀ q₁

0(1) 1(1) 1(1)

1(0) q₂

Рис. 7.6

Состояния q₀ и q₁ заданного автомата неотличимые. Это так поскольку первый символ произвольного входного слова из состояний q₀ и q₁ как начальных перерабатывается одинаково. При этом автомат в обоих случаях переходит в одно и то же состояние. Поэтому дальнейшая переработка слова из начальных состояний q₀ и q₁ продолжается одинаково.

Состояния q₀ и q₂ рассматриваемого автомата являются отличимыми так как, например, (0) (0).

Если состояния q_i и q_j автомата  являются отличимыми, то функции ( ) и ( ) различаются на бесконечном множестве слов.

Действительно, если для некоторого имеет место соотношение ( )  ( ), то для любого слова также справедливо ( ) | ( ).

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

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

Пусть   это автомат с n состояниями, диаграмма переходов которого приведена на рис. 7.7.

0(0) 0(0) 0(0)

0(0)

q₁ q₂ . . . . q_n

1(1) 1(1) 1(1)

1(0)

Рис 7.7

Состояния q₁ и q₂ этого автомата являются отличимыми, и длина кратчайшего слова, на котором они различаются, равна n  1.

Действительно, для любого входного слова первые n  1 символов этого слова одинаково перерабатываются автоматом из состояний q₁ и q_2. После этого  переходит в состояние q_n, если он начал работу из состояния q₂, и в состояние q_n-1, если  начинает работу из состояния q_1. Из q _n-1 и q_n как начальных состояний всякое односимвольное слово перерабатывается по-разному. Поэтому n-й символ любого входного слова перерабатывается из состояний q₀ и q₁ в разные выходные слова.

Покажем, что если состояния q_i и q_j автомата , имеющего n состояний, отличимые, и  это кратчайшее слово, для которого ( ) ( ), то | | n  1.