4.7. Диагностическое дерево

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

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

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

Определение 4.1. Диагностическое дерево есть дерево преемников, в котором ветвь уровня становится оконечной, если удовлетворяется одно из следующих условий: (1) А-группа, связанная с b, содержит кратное -множество. (2) А-группа, связанная с b, связана с некоторой ветвью уровня, предшествующего

Рис. 4.7. Диагностическое дерево для А17 и множества допустимых начальных состояний

Имеется ветвь уровня (возможно, сама ветвь b), связанная с простой А-группой.

Условие (3) подразумевает, что первый уровень, который содержит ветвь, связанную с простой А-группой, является также последним уровнем в диагностическом дереве. Дерево, последний уровень которого является называется деревом высоты k. Рис. 4.7 показывает, как строится диагностическое дерево для автомата представленного на рис. 4.3, и для множества допустимых начальных состояний . Ветвь первого уровня, связанная с А-группой является оконечной в силу правила (1). Очевидно, что на третьем уровне А-группа является простой; поэтому в силу правила (3) все ветви на третьем уровне

являются оконечными. В качестве другого примера на рис. 4.8 показано диагностическое дерево для и множества допустимых начальных состояний Ветвь первого уровня, связанная с А-группой является оконечной в силу правила (1).

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

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

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

Доказательство. Пусть А-группа О состоит из -множеств , где мощность есть . Множество чисел называется распределением размещения G. Число различных А-групп, имеющих то же распределение размещения, что и G, может достигать

Теперь, если обозначено через есть А-группа, связанная с ветвью пути по дереву, то либо распределение

размещения для такое же, как для либо, по лемме 4.1, решение превышает решение Следовательно, если различны и имеют одинаковое решение r, то должно быть либо тождественным с одной из предыдущих А-групп, либо иметь решение По индукции, число последовательных А-групп с решением r или меньшим таких, что никакие две группы не одинаковы, составляет, как максимум, В частности, число последовательных А-групп с решением или менее таких, что никакие две группы не одинаковы, достигает . Следовательно, если различны и не просты, то должна либо быть одинаковой с одной из предшествующих А-групп, либо быть простой. Таким образом, путь, который не заканчивается на ветви в силу правила (2), должен заканчиваться на этой ветви в силу правила (3). Следовательно, никакой путь в диагностическом дереве не может состоять из более чем ветвей, и тем самым лемма доказана.

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

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

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

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

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

Доказательство. Если путь усечен в силу правила (1), то он оканчивается некоторой ветвью b, связанной с А-группой, которая содержит кратное -множество. По лемме 4.1, каждый путь, проходящий через b в дереве преемников, должен приводить к А-группе, которая содержит кратное -множество. Следовательно, такой путь не может вести к простой А-группе и потому не может быть диагностическим путем. Рассмотрим теперь усеченный в силу правила (2) путь, оканчивающийся на уровне ветви которая связана с А-группой О. Тогда должна существовать ветвь уровня, где также связанная с О. По лемме 4,3, если в дереве преемников простая А-группа может быть достигнута из через I ветвей, то простая А-группа также может быть достигнута из через i ветвей. Следовательно, если в дереве преемников диагностический путь проходит через , то через должен также проходить диагностический путь; кроме того, последний должен быть более коротким, чем предыдущий, так как . Следовательно, если дерево преемников содержит диагностический путь, который проходит через то этот путь не может быть описан минимальной диагностической последовательностью.

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

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

диагностические последовательности для М и Так как в силу правила (3) все диагностические пути, представляемые деревом, имеют одинаковую длину, то все они должны быть минимальными. Если диагностическое дерево не представляет диагностических путей, то все эти пути оканчиваются в силу правил (1) и (2), и, следовательно, по лемме 4.6, для не существует диагностической последовательности.