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

Задача определения начального состояния автомата М в случае, когда А(М) имеет произвольную мощность m, конечно, намного сложнее относительно частного случая, когда m = 2. Чтобы различить между собой общий и этот частный случаи, первый будем называть диагностической задачей для m состояний, а второй — диагностической задачей для двух состояний.

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

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

Пусть будут -различимы и -эквивалентны, для некоторого Тогда длина кратчайшей диагностической последовательности для есть l. Любая диагностическая последовательность для длина которой равна определенному выше значению l, будет называться минимальной диагностической последовательностью для и обозначаться . Если -различимы и -эквивалентны, то должны быть разобщенными состояниями в и объединенными в Поэтому I может быть определено путем построения -эквивалентных разбиений для данного автомата М и нахождения наименьшей величины k такой, что содержит в двух различных классах; эта величина должна равняться l.

Когда прикладывается к выходные последовательности получаются одинаковыми, за исключением последнего символа. Следовательно, преемники относительно являются -различимыми и -эквивалентными для всех . Это положение изображено на рис. 4.2, где представлена в виде последовательности

Последовательности состояний, которые проходят автоматы есть соответственно

При этом выходные последовательности имеют вид для автомата

для автомата . Используя обозначения рис. 4.2, можно установить, что если -различимы и -эквивалентны и если есть минимальная диагностическая последовательность для , то: (1) для есть входной символ, который переводит в пару — -различимых и -эквивалентных состояний есть входной символ, при приложении которого к автоматам последние выдают различные выходные символы.

Рис. 4.2. Минимальная диагностическая последовательность для .

Определение Определение когда известны, может быть наиболее удобно произведено с помощью таблиц построение которых для эквивалентных разбиений данного автомата описано в § 3.6. являются -различимыми и -эквивалентными состояниями; следовательно, они составляют смежные строки в таблице и разобщенные строки в таблице . Поэтому строки в таблице должны содержать две клетки, скажем соответственно, которые имеют различные нижние индексы, по меньшей мере в одном, скажем столбце. При этом

должны быть -эквивалентными, так как они являются первыми преемниками -эквивалентных состояний относительно входного символа они должны быть также -различимыми, так как имеют различные нижние индексы в таблице Следовательно, являются искомыми состояниями соответственно, и входной символ есть искомый входной символ Таким образом могут быть определены путем просмотра таблицы

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

Приведенные методы могут быть объединены и представлены в виде следующего алгоритма.

Алгоритм суть два состояния автомата М. Чтобы определить минимальную диагностическую последовательность для . Построим таблицы для М. Найдем I такое, что являются смежными строками в таблице и разобщенными строками в таблице Предположим, что (а) Если , то переходим к шагу 3. (б) Если то соответствует любому столбцу в -подтаблице М, такому, что строки и a j в этом столбце различны. есть минимальная диагностическая последовательность для соответствует любому столбцу в таблице такому, что строки i и этого столбца имеют клетки соответственно с различными нижними индексами. Увеличиваем k на единицу и возвращаемся к шагу (2).

Для иллюстрации рассмотрим автомат представленный таблицей 4.1 и изображенный на рис. 4.3. Таблицы 4.2 — 4.5 являются таблицами и РА автомата Для примера найдем минимальную диагностическую

последовательность для Начнем с рассмотрения таблицы так как это «последняя» таблица, в которой строки 1 и 2 являются смежными. Строки 1 и 2 в таблице имеют различные нижние индексы в клетках которые находятся в столбце . Значит, есть первый символ в (1,2). В таблице строки 4 и 5 имеют различные нижние индексы в клетках , которые находятся в столбце а. Значит, а есть второй символ в В таблице строки 3 и 2 имеют различные нижние индексы в клетках , которые находятся в столбце а. Значит, а есть третий символ в также может быть выбран в качестве третьего символа, так как строки 3 и 2 имеют различные нижние индексы в клетках которые находятся в столбце В -подтаблице строки 1 и 5 имеют различные клетки (0 и 1) в столбце а. Значит, а есть четвертый и последний символ в . Таким образом, имеет

Рис. 4.3. Автомат

Таблица 4.1. Автомат

Таблица 4.2. Таблица

Таблица 4.3. Таблица для

Таблица 4.4. Таблица для

Таблица 4.5. Таблица для

Таблица 4.6. Минимальные диагностические последовательности для пар состояний

вид или . Когда прикладывается к в состоянии 1 и в состоянии 2, последний выходной символ есть 1 и 0 соответственно, что легко может быть проверено по таблице 4.1 или по рис. 4.3. Следовательно, если является множеством допустимых начальных состояний то диагностический эксперимент может быть проведен путем приложения рааа и наблюдения последнего выходного

символа: если этот символ —1, то начальное состояние — 1, если этот символ —0, то начальное состояние таблице 4.6 перечислены все минимальные диагностические последовательности для всех пар состояний последние два столбца в этой таблице указывают последние наблюдаемые выходные символы и когда минимальная диагностическая последовательность прикладывается к соответственно. Хотя для данной пары состояний могут быть построены две или более минимальных диагностических последовательностей, в таблице приведена только одна такая последовательность.