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

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

(см. скан)

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

(см. скан)

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

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

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

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

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

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

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

результат может быть доказан способом, целиком аналогичным способу, примененному в лемме 4.6.

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

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

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