4.17. Следствия, связанные с экспериментами по распознаванию состояний

Особым случаем диагностической или установочной задачи для состояний для автомата М является диагностическая или установочная задача для n состояний, где n есть общее число состояний в М. Эта проблема возникает, когда для М не определены допустимые состояния, и в этом случае следует предполагать, что начальным состоянием может быть любое из n состояний М. Для этого специального случая результаты, полученные в предыдущих параграфах, могут быть видоизменены и обобщены следующим образом.

Следствие 4.3. Пусть М есть автомат с n состояниями и известной таблицей переходов. Если начальное состояние автомата М вообще может быть определено путем проведения простого эксперимента, то оно может быть определено с помощью простого безусловного или простого условного эксперимента длины l, где

Начальное состояние М всегда может быть определено с помощью кратного безусловного эксперимента длины l и кратности с, где

и с помощью сложного условного эксперимента длины l и кратности с, где

Конечное состояние М всегда может быть определено с помощью простого безусловного эксперимента длины l, где

и с помощью простого условного эксперимента длины l и порядка d, где

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

Рис. 4.19. Пара -совместимых состояний.

Теорема 4.14. Пусть М есть автомат с n состояниями и входным алфавитом (а) Если М содержит пару совместимых состояний для каждого входного символа из X, то диагностическая задача для состояний для М никогда не можетбыть решена простым экспериментом. (б) Если М не содержит пары -совместимых состояний ни для какого входного символа из X, то диагностическая задача для n состояний для М. всегда может быть решена простым экспериментом.

Доказательство, (а) Подача любого входного символа на М заставляет пару состояний, скажем перейти

в одно и то же состояние с одинаковыми реакциями и, таким образом, обусловливает то, что эти состояния становятся не различимыми никакими последующими входными символами, (б) По теореме 4.12, М всегда может быть переведен в известное конечное состояние. Пусть установочной последовательностью, примененной для этой цели, является пусть соответствующая выходная последовательность будет а соответствующая последовательность состояний Предположим теперь, что известны для некоторого так как по предположению ни одно состояние в не имеет двух заходящих дуг, несущих одну и ту же пару вход - выход то может быть определено однозначно. Обозначим начальное состояние М через тогда может быть определено рекурсивно на основе знания конечной состояния М и входной и выходной последовательностей, включенных в установочный эксперимент.

Из таблицы переходов заданного автомата М может быть легко установлено, обладает М свойством, упомянутым в части (а), или свойством, упомянутым в части (б) теоремы 4.14. Поэтому эта теорема оказывается во многих случаях полезной для того, чтобы установить, может ли начальное состояние заданного автомата быть определено с помощью простого эксперимента. Когда автомат не имеет ни свойства части (а), ни свойства части (б), то его начальное состояние либо может, либо не может быть определено простым экспериментом.