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

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

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

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

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

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

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

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

Введем предварительно ряд понятий. Под 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 ^*.

2. В 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)-го уровня.

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

 

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: