4.16. Регулярные условные установочные эксперименты

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

Алгоритм 4.8. Даны автомат М и его множество допустимых начальных состояний требуется определить конечное состояние М с помощью простого условного эксперимента. (1) Пусть есть Полагаем k = 0. (2) (а) Если неоднородно, то определяем регулярную подпоследовательность, скажем для Прилагаем к и полагаем, что является подмножеством

которому может быть свойственна наблюдаемая реакция. Пусть есть преемник . Увеличиваем k на 1 и возвращаемся к (2). (б) Если однородно, то конечное состояние М есть состояние, содержащееся в .

Если в алгоритме 4.8 не является однородным, то мощность должна быть меньше, чем мощность . Следовательно, если мощность есть m, то число подпоследовательностей не превышает . Для мощности r всегда имеется регулярная подпоследовательность длина которой не превышает , где есть общее число состояний в М. Следовательно, общая длина установочного эксперимента не может превосходить

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

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

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

Таблица 4.14. Регулярный условный эксперимент для и множества допустимых начальных состояний

Таблица 4.14 демонстрирует регулярный условный эксперимент для показанного на рис. 4.3, и множества допустимых начальных состояний когда истинное начальное состояние есть 4. Первый столбец содержит для справки перечень состояний, через которые проходит по мере проведения эксперимента (эти состояния, конечно, не известны экспериментатору). В этом примере есть есть а. Когда а подается на наблюдаемая реакция есть 1, из которой может быть выведено, что есть . Тогда - преемник g а именно . Подача дает реакцию из которой может быть выведено, что есть . Тогда есть -преемник, а именно Так как однородно, можно сделать заключение, что конечное состояние есть 2.

Рис. 4.17 показывает автомат, обозначенный М, в котором могут быть достигнуты границы теоремы 4.13. Как показано на рисунке, множеством состояний М является входной алфавит есть а выходной алфавит . Выходной символ 1 генерируется только тогда, когда подается в состоянии n. Из структуры М можно увидеть, что если этот автомат, находясь в состоянии подвергается воздействию любого входного символа, отличного от то состояниями - преемниками, соответственно, являются По отношению к установочному дереву для М и множеству допустимых начальных состояний под этим понимается, что кратчайший путь, ведущий из к А-группе, содержащей, по крайней мере, два -множество, есть путь, описывающийся входной последовательностью - группа, к которой ведет этот путь, есть Тогда по индукции кратчайший путь, ведущий от к однородной А-группе, есть путь, описывающийся входной последовательностью длины за которой следует длины за которой следует (длины ). Длина этой последовательности

есть т. е. совпадает с выражением (4.14). Путь ведет к А-группе которая содержит m простых (и, следовательно, однородных) -множество.

(см. скан)

Рис. 4.17. Автомат М.

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

(см. скан)

Рис. 4.18. Установочное дерево для М и множества допустимых начальных состояний

эксперимент для М и множества допустимых начальных состояний должен состоять из m—1 подпоследовательностей, совокупная длина которых задана верхней границей выражения (4.15). Автомат М показывает также, что кратчайший безусловный установочный эксперимент может иметь длину символов.

Заметим, что так как конечная А-группа на рис. 4.18 является простой А-группой, показанный путь описывает минимальную диагностическую последовательность (так же как минимальную установочную последовательность). Поэтому автомат М показывает, что простой безусловный или условный диагностический эксперимент может иметь длину, равную верхней границе l (4.15).