) В § 4.15 будет показано, что такая последовательность всегда существует.

результат может быть доказан способом, целиком аналогичным способу, примененному в лемме 4.6.

Лемма 4.8. Усеченные пути установочного дерева, построенного для М и А(М), не описывают минимальных диагностических последовательностей.

Таким образом, мы имеем следующую теорему - аналог теоремы 4.2.

Теорема 4.10. Множество последовательностей, описываемых установочными путями в установочном дереве, построенном для автомата М и множества допустимых начальных состояний А (М), есть множество всех минимальных установочных последовательностей для М и А(М).

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

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

Алгоритм 4.6. Даны автомат М и его множество

допустимых начальных состояний Л (714) = a,j, о,.....im}

требуется найти конечное состояние М с помощью кратчайшего простого безусловного эксперимента. (1) Строим установочное дерево для М и А{М). (2) Выбираем любую установочную последовательность (А), описываемую деревом ).

(3) Составляем перечень реакций Л1а, Л1а.....Im

на (А) и состояний о о......о в которые соответ-

ственно переходят о, О;.....о при подаче {А).

(4) Прилагаем (А) к УИ и фиксируем реакцию. Конечное

состояние есть состояние о, , для которого реакция, внесен-

пая в перечень ц (3), совпадает с зафиксированной реакцией.

Алгоритм 4.5 может быть продемонстрирован на примере автомата Л17 (рис. 4.3) и множества допустимых начальных состояний {1, 2, 3, 4, 5}. В этом случае установочное дерево на рис. 4.16 выявляет, что минимальмя устацрзочная последовательность есть ааа. Таблица 4.11 содержит перечень

4.14] ПРОСТЫЕ УСЛОВНЫЕ УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ 165

Таблица 4.11 Реакция Л17 на ааа

реакций и конечных состояний для начальных состояний (1, 2, 3, 4, 5}, когда применяется ааа. Как" и следовало ожидать, различные конечные состояния соответствуют различным реакциям и, следовательно, реакции могут служить в качестве критериев для распознавания конечного состояния Л17 при условии, что определено множество допустимых начальных состояний.

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

или автомат Жд, в состоянии, принадлежащем множеству А{Мр). Желательно распознать автомат и его конечное состояние. Если предположить, что

Ml, М2..... Ждг являются сравнимыми и что их таблицы

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

начальных состояний А (Mi) [} А (М2) U • • U А (М). В этом случае в основном предположении, что заданный автомат М является минимальным, подразумевается, что каждый автомат Ml является минимальным и что ни одно состояние любого автомата Mi не является эквивалентным какому-нибудь состоянию автомата Mj (J ф 1).

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

Рассмотрим путь в установочном дереве для М и Л(Л1), который ведет к Л-группе О, содержащей однородное о-множество, скажем 0, .....oj, где о встречается h раз

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

ЧИСЛО h состояний, скажем о, о,-, о, все преемники которых по отношению к W суть о. Так как а, о, ..., oj является однородным в О, то реакция о,- или о,-.....или о-

на , по лемме 4.2, не может быть приписана никакому конечному состоянию, за исключением а[. Следовательно,

если или О;.....или о,- случайно является истинным

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

Расчленение минимальной установочной последовательности на подпоследовательности выполняется следующим образом. Пусть является /г-й подпоследовательностью и пусть 0 является Л-группой, к которой ведет путь, описывающийся последовательностью 12 • • • k обозначим А{М) через Gq. Тогда есть последовательность, описываемая подпутем, который ведет от 0-\ к первой Л-группе, которая содержит, по крайней мере, на одно однородное а-множество больше, чем 0-\- Так как решение Gq есть 1 и так как число о-множеств в Л-группе не может превышать мощность А{М), равную т, число подпоследовательностей, произведенных таким образом, не может превышать т- 1. Например, автомат Л17, представленный на рис. 4.3, и множество допустимых начальных состояний {1, 2, 3, 4, 5} дают: Go={l, 2, 3, 4, 5}; Gi={l, 1}, {2}, {5. 1}; G2={1. 1}. {1}. {2}. (М- и. еле-довательно, i = aa, а 2 = 1 (см. рис. 4.16). Если определены подпоследовательности, условный эксперимент может быть выполнен следующим образом.

Алгоритм 4.6. Даны автомат М, его множество допустимых начальных состояний Л(Л1) = а,-, о.....oj и

расчлененная установочная последовательность Wii • распознать конечное состояние М с помощью условного эксперимента. (1) Составляем перечень реакций M\ai, M\ai, ...