ОПРЕДЕЛЕНИЕ. Состояния qi и qj автомата Áназываются отличимыми, если существует такое входное слово , что

Состояния qi и qj автомата Áназываются отличимыми, если существует такое входное слово , что

( ) ( ).

 

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

 

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

 

0(0) 0(0)

q0 q1

 

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

 

1(0) q2

Рис. 7.6

 

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

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

 

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

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

 

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

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

 

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

 

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

0(0)

q1q2 . . . . qn

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

 

 

1(0)

 

Рис 7.7

Состояния q1 и q2 этого автомата являются отличимыми, и длина кратчайшего слова, на котором они различаются, равна n - 1.

Действительно, для любого входного слова первые n - 1 символов этого слова одинаково перерабатываются автоматом из состояний q1 и q2. После этого Á переходит в состояние qn, если он начал работу из состояния q2, и в состояние qn-1, если Á начинает работу из состояния q1. Из q n-1 и qn как начальных состояний всякое односимвольное слово перерабатывается по-разному. Поэтому n-й символ любого входного слова перерабатывается из состояний q0и q1 в разные выходные слова.

 

Покажем, что если состояния qi и qj автомата Á, имеющего n состояний, отличимые, и -это кратчайшее слово, для которого ( ) ( ), то | | n - 1.

 








Дата добавления: 2015-09-18; просмотров: 699;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.