4,9] ПРОСТЫЕ УСЛОВНЫЕ ДИАГНОСТИЧ, ЭКСПЕРИМЕНТЫ 149

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

Уровень I

а I f

{5.ff},{Ze> {Ш4}

2 {9.9}.{6}.{7} т{7},Щт

Рис. 4.11. Диагностическое дерево для А2\ и множества допустимых начальных состояний {1. 2, 3, 4}.

могут быть приписаны прошлые реакции. В терминах дерева преемников это означает, что путь, который ведет к Л-группе, содержащей кратное а-множество, может быть еще использован для построения диагностического эксперимента, так как кратное а-множество может быть получено из допустимых состояний, которые были ранее исключены. Этот факт демонстрируется диагностическим деревом для автомата Л21 и множества допустимых начальных состояний {1, 2, 3, 4), показанным на рис. 4.11. Хотя пути, описывающие аа и ар, ведут к Л-группам, содержащим кратные а-множества {9, 9) и {10, 10} соответственно, эти а-множества могут быть исключены на основе реакции на первый символ а; после того как приложено а, могут быть исключены или состояния 1 и 2, как допустимые состояния (в этом случае можно пренебречь (9, 9)), или состояния 3 и 4 (в этом случае можно пренебречь {10, 10}).

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

Л(Л1)=[а,, а,.....a,J

может быть реализован, если дерево преемников для М и А{М) содержит т путей, природа которых указана на рис. 4,12. На этом рисунке о обозначает преемника о, ;

любой из т путей, показанных на рисунке, может полностью перекрывать какой-либо из остальных путей, В добавление

А(М)

I {el,} {s;,} (el,)

Рис, 4,12. Пути для простого условного диагностического эксперимента.

к таким путям простой условный эксперимент требует ряда правил: (1) правило для выбора первого входного символа в эксперименте; (2) правило выбора (/г+-го входного символа в эксперименте при условии, что дана реакция на предыдущие k символов; (3) совокупность правил, которые должны давать в результате входную последовательность, описываемую путем, заканчивающимся в \а. ] (й=1, 2.....т),

если истинное начальное состояние есть состояние о из А{М).

Посредством доказательства, подобного доказательству леммы 4,4, может быть показано, что если множество путей длины {т - 1)п" или меньшей не имеет свойств, отмеченных на рис. 4.12, то никакое множество путей любой длины не имеет этих свойств. Таким образом, мы имеем следующую теорему.

Теорема 4.5. Если диагностические задачи для автомата с п состояниями и т допустимыми состояниями вообще могут быть решены путем проведения простого условного эксперимента, то они могут быть решены

С помощью простого условного эксперимента длины I, где /<(/я -1)я". (4.6)

Для того чтобы определить, может ли быть реализован простой условный эксперимент для заданных МкА {М), определяют сначала, существует ли требуемое множество путей. Если это так, то составляют перечень всех возможных совокупностей правил для выбора входной последовательности. Если существует совокупность правил, которые выполняют оговоренные выще условия (1), (2) и (3), то такой эксперимент существует, и эта совокупность может быть использована для его выполнения. Если совокупность правил, удовлетворяющая этим условиям, не существует, то диагностическая задача для М и А (М) не может быть решена с помощью простого условного эксперимента. По теореме 4.4, из этого следует, что задача не может быть решена никаким простым экспериментом - безусловным или условным.

Чтобы убедиться в том, что имеются случаи, когда диагностическая задача не может быть решена никаким простым экспериментом - безусловным или условным, рассмотрим автомат Л21 на рис. 4.10 и множество допустимых начальных состояний {5, 6, 7, 8). Любая последовательность или подпоследовательность, начинающаяся с а, заставляет состояния 5 и 6 перейти в состояние 9 с одинаковыми реакциями; любая последовательность или подпоследовательность, начинающаяся с р, заставляет состояния 7 и 8 перейти в состояние 10 с одинаковыми реакциями. Следовательно, уже после приложения первого входного символа (для того чтобы начать безусловный или условный эксперимент) нет возможности когда-либо различить состояние 5 и 6 или состояние 7 и 8. Таким образом, мы имеем следующую теорему.

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

4.10. Кратные безусловные диагностические эксперименты

Очевидный недостаток простого эксперимента заключается в том, что он может оказаться разрушительным; действительно, если имеется только один экземпляр автомата, то,