4.2. Диагностические и установочные эксперименты

Автомат S, таблица состояний и выходов которого задана, находится в начале эксперимента в одном из состояний ai ... aj . Сформулируем две задачи.

Диагностическая задача. Требуется найти состояние автомата в начале эксперимента.

Установочная задача. Требуется установить S в состояние, которое известно.

Диагностическая задача есть задача определения начального состояния S, а установочная задача состоит в определении конечного состояния S.

Эксперимент, который решает диагностическую задачу, называется диагностическим; установочную задачу – установочным. Ясно, что каж-дый диагностический эксперимент есть также установочный экспери-мент, так как знание начального состояния S и приложенной последова-тельности означает знание конечного состояния. Обратное не обязательно верно.

Множество состояний {a₁ ... a_m}, одно из которых, как известно экс-периментатору, есть начальное состояние S, называется множеством допустимых начальных состояний и обозначается А(S). Как диагностическая, так и установочная задачи становятся тривиальными, когда А(S) является одноэлементным множеством, т.е. когда m=1. Наше внимание будет сконцентрировано на случаях, когда m2.

4.2.1. Дерево преемников

Введем предварительно ряд понятий. Под a-множеством автомата S будем понимать любое конечное множество его состояний, причем элементы этого множества не обязательно различны. Множество, состоящее из единственного элемента, называется простым; содержащее два или более одинаковых элементов - кратным. Множество назовём однородным, если оно состоит из одинаковых элементов. Например, множество {a3} простое, {a2, a3, a2} – кратное, {a3, a3, a3} – однородное.

A-группа есть множество a-множеств автомата S, в котором число элементов во всех входящих в A-группу a-множеств равно m и совпадает с числом элементов в А(S). A-группа называется простой, если все a-множества в ней простые, однородной, если все a-множества в нём однородные.

Предположим, что G есть A-группа, содержащая a-множества σ1, …, σr. Тогда z_i¹ z_i²...z_i^k -преемником G будет другая A-группа, построенная согласно следующим правилам:

1. Разбиваем каждое множество σ_i на такие подмножества, что два состояния σ_i включаются в одно и то же подмножество тогда и только тогда, когда они вырабатывают одинаковые реакции на входную последовательность z_i¹ z_i²...z_i^k. Считаем каждое подмножество как σ-множество, а множество всех таких множеств как A-группу, обозначенную через G ^*.

1. В a-множествах из G ^* заменяем каждое состояние его преемником относительно входной последовательности z_i¹ z_i²...z_i^k. Полученная A-группа есть z_i¹ z_i²...z_i^k- преемник G.

Дерево преемников есть структура, определенная для данного автомата S и заданного множества допустимых начальных состояний A(S). Структура состоит из ветвей, расположенных в последовательных уровнях, причем высшим уровнем является "нулевой", следующий за высшим является "первый" уровень и т. д. Нулевой уровень дерева содержит единственную ветвь, называемую начальной ветвью.

В дереве преемников, построенном для автомата с входным алфавитом {Z₁,...,Z_p}, каждая ветвь в k-м уровне (k  0) расщепляется на p ветвей, представляющих Z₁,...,Z_p соответственно и являющихся ветвями в (k +1)-м уровне. Ветвь, представляющая входной символ z_i , называется "ветвью z_i".

Путем по дереву называется последовательность из l таких ветвей, что каждая следующая порождается предыдущей. Если k-я ветвь этого пути есть z_i^k, то говорят, что этот путь описывает входную последовательность z_i¹,...,z_i^k. Таким образом, первые (k + 1) уровней дерева преемников содержат p^k путей, описывающих все возможные входные последовательности длиной k, которые могут быть построены из p входных символов.

Каждая ветвь в дереве преемников, построенном для S и A(S), связана с A-группой, с начальной ветвью связана A(S). Если ветвь b связана с A-группой G, то ветвь z_i, которую порождает b, связана с z_i - преемником G. A-группы, связанные с ветвями k-го уровня (k  1), могут быть определены из A-групп, связанных с ветвями (k-1)-го уровня.

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