а его высота есть 2. Таким образом, 1 экземпляров

Л23 требуется для решения задачи с помощью безусловного эксперимента и только 2 экземпляра для решения задачи путем условного эксперимента.

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

4.12. Установочное дерево

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

Таблица 4.10

Автомат Д23

Уровень

\ffg,=UZ,...,m}

I S(J,m)=a

/123

ff„={l2} &(J.2)=/S

5Ггг-<ЗМ

есз.4)=д

т/г-t

дгзЧЗе} 8(3.3) =fi

Srr,m/Z-r<"-3 2} S(m-3,m-2)=fl

A23 m/2-7\ m/2

ёСт~7,т/=Д

77/2\m/2*7

£7гг=} =(2/ &гз(3} ff24={4} дггЧЗ) ffff{3} дгг,т-з=("-3} дг.т-г=("- ff2.m-t=<"-}5Гг.т=(">

Рис. 4.15. Дерево кратного эксперимента для Л23 и множества допустимых начальных состояний

{1, 2, ...,т}.

Уровень О

{7,2,34.5} \

{7.15}, (32}.

{4,57,4,5}

{7.7} {2} {5.7} а. 1

{4,4,5} {7.5}

{32.3,2}, {7}

{4.5,4.4.5} I I

I I Г - I I - I 1П

3 {1,7} {7},{2},{7} {4.4},{5}.{54} {3,3.2}{7}{2} {4,4.5}{<5J {5.7.5.7} {7} {7.5,15}{4} {3.2,3.3.2} {4.5.4.4.5}

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

{1, 2. 3, 4, 5}.

m о S S га

о >

§

со >

>

п о п

Определение 4.2. Установочное дерево есть дерево преемников, в котором ветвь b k-то уровня становится оконечной, если выполняется одно из следующих условий: (1) Л-группа, связанная с Ь, является связанной с некоторой ветвью в уровне, предшествующем /г-му. (2) Имеется ветвь /г-го уровня (возможно, сама Ь), связанная с однородной Л-группой.

Правило (2) подразумевает, что первый уровень, который содержит ветвь, связанную с однородной Л-группой, также является последним уровнем в установочном дереве. Рис. 4.16 демонстрирует, как строится установочное дерево для автомата Л17, представленного на рис. 4.3, и множества допустимых начальных состояний {1, 2, 3, 4, 5}. Очевидно, что в третьем уровне Л-группа {1, 1}, {1}, {2}, {1} является однородной; поэтому в силу правила 2 все ветви в третьем уровне являются оконечными.

Посредством доказательства, аналогичного доказательству, примененному в лемме 4.4, можно показать, что длина любого пути в установочном дереве для автомата Men состояниями и т допустимыми состояниями не может превышать {т - \)п". Поэтому построение установочного дерева есть конечный процесс. В следующем параграфе будет получена граница, которая существенно ниже, чем {т-\)п".

Установочным путем будет любой путь в установочном дереве, оконечная ветвь которого связана с однородной Л-группой. Установочной последовательностью Am М и А{М) будет любая входная последовательность, которая, будучи приложенной к M\oi и M\Oj, где о,- и Oj суть два состояния в А{М), дает две различные выходные последовательности, если она переводит о и Оу в два различных состояния. Тогда лемма 4.2 дает следующую лемму.

Лемма 4.7. Входная последовательность, описываемая установочным путем в установочном дереве, построенном для М и А{М), есть установочная последовательность для М и А{М).

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