4.8] ПРОСТЫЕ БЕЗУСЛОВНЫЕ ЭКСПЕРИМЕНТЫ 143

ные диагностические последовательности для М и А{М). Так как в силу правила (3) все диагностические пути, представляемые деревом, имеют одинаковую длину, то все они должны быть минимальными. Если диагностическое дерево не представляет диагностических путей, то все эти пути оканчиваются в силу правил (1) и (2), и, следовательно, по лемме 4,6, для М и Л(УИ) не существует диагностической последовательности.

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

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

Алгоритм 4.2. Даны автомат М и его множество допустимых начальных состояний

А (М) = {oi, о,......о,

Требуется найти начальное состояние М с помощью кратчайшего простого безусловного эксперимента. (1) Построим диагностическое дерево для М и А (УИ). (2) Найдем любую диагностическую последовательность ё{А), описываемую этим деревом. Если ни одна такая последовательность деревом не описывается, то не существует решения с помощью простого безусловного эксперимента. (3) Перечислим реакции

Маг,, M\Oi.....Iim Подадим (Л)

на Л1 и зафиксируем реакцию. Начальным состоянием автомата является состояние о, для которого реакция, упомянутая в (3), совпадает с зафиксированной реакцией.

Алгоритм 4.2 может быть продемонстрирован на примере автомата Л17, показанного на рис. 4.3, и множества допустимых начальных состояний {2, 3, 4, 5}. В этом случае диагностическое дерево, представленное на рис. 4.7, показывает, что минимальной диагностической последовательностью является последовательность ааа. В таблице 4.7 перечислены реакции состояний 2, 3, 4 и 5 на ааа. Эти реакции, как можно было ожидать, являются различными

Таблица 4.7 Реакции АП на ааа

И могут служить в качестве критерия для распознавания начального состояния Л17, когда оно принадлежит заданному множеству допустимых начальных состояний. Другой пример приведен на рис. 4.8, выявляющем, что минимальными диагностическими последовательностями для Л17 и множества допустимых начальных состояний {1, 2) являются последовательности рааа и рара. Для т = 2 диагностическая задача сводится к диагностической задаче для двух состояний, для которой по теореме 4,1 всегда существует решение с помощью простого безусловного эксперимента. В этом случае минимальная диагностическая последовательность может быть более удобно определена через таблицы Р, как описано в § 4.4. Для /я > 2 решение посредством простого безусловного эксперимента существует не всегда, как показано с помощью диагностического дерева для Л17 и множества допустимых начальных состояний (1, 2, 3, 4, 5), изображенных на рис. 4.9.

Используя лемму 4,4, мы теперь можем подвести следующие итоги.

Урове д I

О {].ZA4,5}

; {1.}.5}Мг}

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

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

Z<(w-1}я", (4.5)

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

Решение диагностической задачи для т состояний непосредственно может быть применено к следуюш,ей задаче: известно, что данный автомат М является автоматом в состоянии, принадлежаш,ем множеству А{М{), или автоматом М2 в состоянии, принадлежаш,ем множеству А (AIj).....

или автоматом Mj в состоянии, принадлежаш,ем множеству Л(Л1дг). Требуется распознать автомат М и его начальное состояние. В предположении, что AJj, М2..... Mjy

являются сравнимыми и для них имеются таблицы переходов, вышеупомянутая задача в точности представляет собой диагностическую задачу для т состояний для расщепляемого автомата А (Ml, М2..... УИдг) и множества допустимых начальных состояний А (Ml) и А {М2) и UA{M). Основное предположение о том, что данный автомат М является минимальным, в данном случае означает, что каждый автомат УИ,. минимален и что ни одно состояние в автомате не является эквивалентным ни одному состоянию в автомате УИу U 4= I)-

4.9. Простые условные диагностические эксперименты

Рассмотрим в диагностическом дереве для УИ и Л(УИ) путь, который ведет к Л-группе О, содержащей простое а-множество, например а] (сама О не обязательно является простой, так как она может содержать другие непростые о-множества). Если этот путь описывает входную последовательность , то А{М) должно содержать состояние, например о, преемником которого по отношению к является состояние о. Так как множество а} в О является одноэлементным, то реакция о,, на , по лемме 4,2, не может быть приписана никакому состоянию из А{М), за исключением о. Следовательно, если случайно является истинным начальным состоянием М, то его можно распознать входной последовательностью, которая не обязательно описывается диагностическим путем. Используя этот факт, можно применять минимальные диагностические последовательности по частям, а не целиком, в надежде, что начальное состояние таково, что его можно распознать с использованием лишь части всей последовательности. Эта схема составляет решение диагностической задачи для т состояний с помощью простого условного эксперимента.