Уровень

f ffJ} {4,5} „

{3,2} {4.5}

3 {5.7) {1,5}

/ {2>.{!) (34} {7},{Z} {4.5}

Рис. 4.8, Диагностическое дерево для Л17 и множества допустимых начальных состояний (1, 2).

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

Лемма 4.4. Высота диагностического дерева, построенного для автомата Men состояниями и множества допустимых начальных состояний мощности т, определяется величиной h, где

h{m - l)n". (4.3)

Доказательство. Пусть Л-группа О состоит из о-множеств gi, g2.....gr, где мощность gi есть от,. Множество

чисел OTj, т2.....т называется распределением размещения О. Число различных Л-групп, имеющих то же распределение размещения, что и О, может достигать

я"я"2 ... п"г = п.- (4.4)

Теперь, если Л (Ж) обозначено через Oq, а 0 есть Л-группа, связанная с /г-й ветвью пути по дереву, то либо распреде-

ЯВЛЯЮТСЯ оконечными. В качестве другого примера на рис. 4.8 показано диагностическое дерево для Л17 и множества допустимых начальных состояний {1, 2). Ветвь первого уровня, связанная с Л-группой {1, 1), является оконечной в силу

4,?1 ДИАГНОСТИЧЕСКОЕ ДЕРЕВО 141

ление размещения для 0 такое же, как для Oj i, либо, по лемме 4.1, решение 0 превышает решение Oft i. Следовательно, если Oj, Оу,.....Oym j различны и имеют

одинаковое решение г, то Ojm должно быть либо тождественным с одной из предыдущих Л-групп. либо иметь решение г>-г+1- По индукции, число последовательных Л-групп с решением г или меньшим таких, что никакие две группы не одинаковы, составляет, как максимум, гп". В частности, число последовательных Л-групп с решением т - 1 или менее таких, что никакие две группы не одинаковы, достигает (т. - !)«". Следовательно, если Oq, Oj, ...

Oj jjm j различны и не просты, то 0 ,должна либо быть одинаковой с одной из предшествующих Л-групп, либо быть простой. Таким образом, путь, который не заканчивается на [{т - 1)й"]-й ветви в силу правила (2), должен заканчиваться на этой ветви в силу правила (3). Следовательно, никакой путь в диагностическом дереве не может состоять из более чем (т. - !)«" ветвей, и тем самым лемма доказана.

Во всех конкретных случаях h существенно меньше, чем граница, выраженная формулой (4,3). так как в формулу (4.3) мы не включили влияние правила (1) на длину пути или влияние на длину пути Л-групп, связанных с другими путями. Лемма 4.4 доказывает, по крайней мере, что число уровней в диагностическом дереве конечно и что поэтому построение такого дерева представляет собой конечный процесс.

Диагностическим путем будем называть любой путь в диагностическом дереве, оконечная ветвь которого связана с простой Л-группой. Диагностической последовательностью для Ж и Л(Ж)=о(. 0(.....0(} будем называть

любую входную последовательность, которая, будучи приложена к М О/. Ж I о,-.....Жа(, дает в результате т

различных выходных последовательностей. Тогда из леммы 4.2 следует

Лемма 4.5. Входная последовательность, описанная диагностическим путем в диагностическом дереве, построенном для М и Л (Ж), есть диагностическая последовательность для Ж и Л (Ж).

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

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

Доказательство. Если путь усечен в силу правила (1), то он оканчивается некоторой ветвью Ь, связанной с Л-группой, которая содержит кратное а-множество. По лемме 4.1, каждый путь, проходящий через b в дереве преемников, должен приводить к Л-группе, которая содержит кратное а-множество. Следовательно, такой путь не может вести к простой Л-группе и потому не может быть диагностическим путем. Рассмотрим теперь усеченный в силу правила (2) путь, оканчивающийся на у-м уровне ветви bj, которая связана с Л-группой О. Тогда должна существовать ветвь Ь i-TO уровня, где / < j, также связанная с О. По лемме 4.3, если в дереве преемников простая Л-группа может быть достигнута из bj через I ветвей, то простая Л-группа также может быть достигнута из ft,- через / ветвей. Следовательно, если в дереве преемников диагностический путь проходит через bj, то через Ь должен также проходить диагностический путь; кроме того, последний должен быть более коротким, чем предыдущий, так как / < у. Следовательно, если дерево преемников содержит диагностический путь, который проходит через bj, то этот путь не может быть описан минимальной диагностической последовательностью.

Теорема 4.2. Множество последовательностей, описываемых диагностическими путями в диагностическом дереве, построенном для автомата М и множества допустимых начальных состояний Л (Ж), представляет собой множество всех минимальных диагностических последовательностей для М и для А{М).

Доказательство. По лемме 4.6 множество диагностических путей, представляемых диагностическим деревом, должно содержать пути, которые описывают все минималь-