ТОЛЬКО два экземпляра АП. Как легко можно установить, диагностическая задача для Л17 и множества допустимых

Sro,= (l2.....mi

1 9гг(3,3,....т} 1 Sf2.3),

9s,=<2}

1 &2г=(3.4,.... m>

ij(m-2m-V=i.,

Рис. 4.14. Дерево кратного эксперимента для А22 и множества допустимых начальных состояний {1,2.....т].

начальных состояний {1, 2, 3, 4, 5) не может быть решена простым экспериментом, и, следовательно, приведенное выше упрощение обеспечивает достижение наименьшей возможной кратности для этой задачи.

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

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

Алгоритм 4.4. Даны автомат М, его множество допустимых начальных состояний Л (УИ) = {ог, о,.....Ог и

дерево кратного эксперимента для М и А(М); требуется найти начальное состояние УИ с помощью кратного условного эксперимента. (1) Приложим входную последовательность, указанную для начальной ветви, к первому экземпляру УИ. Пусть k = 2. (2) Перейдем к ветви, для которой перечисленная выходная последовательность совпадает с реакцией, данной последней примененной входной последовательностью. (3) (а) Если ветвь не является оконечной, то приложим входную последовательность, указанную для этой ветви, к k-y экземпляру УИ. Увеличим /г на 1 и вернемся к (2). (б) Если ветвь оконечная, то одноэлементное множество [Otj, связанное с этой ветвью, содержит начальное состояние М.

Действие алгоритма 4.4 состоит в том, чтобы вести

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

в (о; 1. где о> есть истинное начальное состояние УИ. I я J п

Следовательно, устраняется необходимость в тех экземплярах М, которые не появляются вдоль этого пути.

Алгоритм может быть продемонстрирован деревом кратного эксперимента на рис. 4.13. Если истинное начальное состояние Л17 есть 3, то приложение а к первому экземпляру Л17 дает О, который ведет к ветви, связанной с (1, 2, 3). Соответственно последовательность, примененная ко второму экземпляру, есть аа, что дает 01 и, следовательно, ведет к ветви, связанной с (3). Тогда можно заключить, что начальное состояние Л17 есть 3.

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

это ЧИСЛО не может превышать общего числа экземпляров в дереве. Тогда, по теореме 4.8, кратность кратного условного эксперимента не превышает т-1. Если индивидуальные диагностические последовательности построены возможно более короткими, то, по теореме 4.7, длина эксперимента не может превосходить

5](/г-г+1) = (й+1)(А«-1)-2г =

г=2 г=2

= (2л т)(,я-1). (4.9)

Следовательно, мы имеем теорему.

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

11(2п - т)(т-1), (4.10)

с</я -1. (4.11)

Граница в (4.10) может быть достигнута для т = 2 и любого л 2. Граница в (4.11) может быть достигнута для любого п и да <; л, как показано на примере автомата Л22 в таблице 4.9 и дерева кратного эксперимента на рис. 4.14: если начальное состояние Л22 есть либо т-1, либо да, то для диагностической задачи для Л22 и множества допустимых начальных состояний {1, 2.....да) требуется в точности т-1 экземпляров.

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

множества допустимых начальных состояний (1, 2.....да)

(где 2 < да < л - 1 и где как т, так и л являются четными) показано на рис. 4.15. Очевидно, что число экземпляров,

включенное в дерево кратного эксперимента, есть -+1,