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

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

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

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

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

и могут служить в качестве критерия для распознавания начального состояния когда оно принадлежит заданному множеству допустимых начальных состояний. Другой пример приведен на рис. 4.8, выявляющем, что минимальными диагностическими последовательностями для и множества допустимых начальных состояний являются последовательности рааа и рсфа. Для диагностическая задача сводится к диагностической задаче для двух состояний, для которой по теореме 4,1 всегда существует решение с помощью простого безусловного эксперимента. В этом случае минимальная диагностическая последовательность может быть более удобно определена через таблицы как описано в § 4.4. Для решение посредством простого безусловного эксперимента существует не всегда, как показано с помощью диагностического дерева для и множества допустимых начальных состояний изображенных на рис. 4.9.

Таблица 4.7

Реакции

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

Рис. 4,9. Диагностическое дерево для и множества допустимых начальных состояний

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

Решение диагностической задачи для состояний непосредственно может быть применено к следующей задаче: известно, что данный автомат М является автоматом в состоянии, принадлежащем множеству или автоматом в состоянии, принадлежащем множеству или автоматом в состоянии, принадлежащем множеству Требуется распознать автомат М и его начальное состояние. В предположении, что являются сравнимыми и для них имеются таблицы переходов, вышеупомянутая задача в точности представляет собой диагностическую задачу для m состояний для расщепляемого автомата и множества допустимых начальных состояний Основное предположение о том, что данный автомат М является минимальным, в данном случае означает, что каждый автомат минимален и что ни одно состояние в автомате не является эквивалентным ни одному состоянию в автомате