СОСТОЯНИЙ [Oj, О;}, использованной для разбиения g,

является {1, 4). В данном случае пара состояний выбрана таким образом, чтобы она дала кратчайшее возможное (Оу, о,) (однако это правило выбора в данном методе несущественно). Выбор можно произвести с помощью перечня последовательностей, записанного в таблице 4.6, где (1,4), очевидно, есть а. Когда а приложено к Л17, подмножество 1, 2, 3) множества g отвечает реакцией О, а подмножество 4, 5} - реакцией 1, что легко может быть выведено из таблицы переходов или диаграммы для Л17. Поэтому начальная ветвь расщепляется на две ветви: ветвь, обозначенную О, что является характеристической реакцией gii={l,2, 3} по отношению к (1, 4) = а, и ветвь, обозначенную 1, что является характеристической реакцией 12= {4, 5) по отношению к (1, 4) = а. Теперь из g выбирается пара состояний {1, 3} таким же образом, как {1, 4) была выбрана из gQi- Когда к Л17 приложено (1, 3) = аа, подмножество (1,2} из gii отвечает реакцией 00, а подмножество [3} из gii отвечает реакцией 01. Поэтому ветвь, представляющая gii, расщепляется на две ветви: ветвь, обозначенную 00, что является характеристической реакцией g2i={U 2} по отношению к (1, 3) = аа, и ветвь, обозначенную 01, что является характеристической реакцией 22= {3} (1, 3) = аа. Последняя ветвь является оконечной, так как 22 является одноэлементным множеством. Остаток дерева развертывается аналогичным образом.

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

Для л 17 и его множества допустимых начальных состояний {1, 2, 3, 4, 5) используются четыре экземпляра. Эти экземпляры, обозначенные 17i, Л172, з- 4 подвергаются воздействию диагностических последовательностей а, аа, ааа и роаа соответственно, как предписывается деревом сложного эксперимента па рис. 4.13. Если теперь оказывается, что начальное состояние Л17 есть 2, то Л171 должен дать О, Л172 должен дать 00 и Л174 должен дать 1100. Так как эти реакции удовлетворяют реакциям, указанным вдоль пути по дереву, оканчивающегося в§з2={2), начальное состояние распознается как 2.

Очевидно, что действие экземпляра М, связанного с множеством gj,, состоит в том, чтобы «расщепить» это множество на два или более подмножеств. Так как число расщепляющих операций, требуемых для того, чтобы разделить А{М) на т одноэлементных подмножеств, не превышает /и-1, число экземпляров, включенных в дерево кратного эксперимента, не превышает т - 1. Так как длина диагностической последовательности для пары состояний в машине с п состояниями не может превосходить п - 1, общая длина всех последовательностей, включенных в дерево, не может превышать (я-1) (/я-1). Таким образом, мы имеем следующую теорему.

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

/<(л -1)(/и -1), (4.7)

с</я -1. (4.8)

Граница в (4.7) существенно выше, чем величина /, встречавшаяся в большинстве задач (хотя она может быть достигнута для от =2), так как, по теореме 4.7, только часть примененных последовательностей должна быть длины п-1. Однако граница в (4.8) может быть достигнута при каждом п и тп, как показано на примере автомата Л22 с п состояниями (таблица 4.9).

Так как каждый входной символ переводит все состояния Л22 в состояние 1, все диагностические последовательности ограничиваются одним символом. Так как каждый входной

символ способен выполнить в точности одну операцию «расщепления» множества допустимых начальных состояний (независимо от мощности этого множества), диагностический эксперимент для т состояний для А22 требует в точности т-1 экземпляров. Дерево кратного эксперимента для А22

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

показано на рис. 4.14.

Можно отметить, что, хотя метод построения кратного эксперимента может минимизировать длину входной последовательности, прикладываемой к каждому экземпляру, он, вообще говоря, не минимизирует общую длину эксперимента или его кратность. Во многих случаях как длина, так и кратность эксперимента могут быть сокращены посредством использования следующего очевидного факта. Если даны две входные последовательности и ij- то реакция автомата М на 1 может быть определена по реакции М на i-Таким образом, если как так и 12 являются диагностическими последовательностями, которые должны применяться в кратном эксперименте, то в действительности должна применяться только 12- Например, в кратном эксперименте, описанном на рис. 4.13, реакции Л171 па а и Л1/2 на аа могут быть определены по реакции Л1/3 на ааа; следовательно, для эксперимента в действительности требуется

Таблица 4.9

Автомат Л22