Главная  Кибернетика 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [ 39 ] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

4.3] ДИАГНОСТИЧЕСКИЕ И УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ 125

разделенных операциями принятия решений), из которых состоит эксперимент. Кратность эксперимента есть число экземпляров автомата, требующихся при исследовании. Так, безусловный эксперимент есть эксперимент порядка 1, а условный эксперимент есть эксперимент порядка 2 или более. Простой эксперимент есть эксперимент кратности 1, а кратный эксперимент есть эксперимент кратности 2 или более. Длина, порядок и кратность эксперимента могут рассматриваться как грубые меры его стоимости.

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

Наша основная цель в этой главе состоит в разработке экспериментов для решения следующих двух задач,

1. Диагностическая задача. Известно, что данный автомат М, таблица переходов которого имеется в нашем распоряжении, находится в одном из состояний Oi, ai.....о/.

Найти это состояние.

2. Установочная задача. Известно, что данный автомат М, таблица переходов которого имеется в нашем распоряжении, находится в одном из состояний О/, О/.....0/.

Установить М в известное состояние,

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

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



Множество состояний

рых, как известно экспериментатору, есть начальное состояние М, называется множеством допустимых начальных состояний и обозначается А(М). Состояния А{М) называются допустимыми состояниями. Как диагностическая, так и установочная задачи становятся тривиальными, когда А{М) является одноэлементным множеством, т. е. когда /к=1. Наше внимание, следовательно, будет сконцентрировано на случаях, когда /к 2.

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

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

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

В этой главе мы рассмотрим диагностическую задачу для двух состояний, предполагая, что данный автомат М имеет п состояний, с А{М)= [oi, OyJ. Так как М минимален, то

и Оу-, должны быть различимы и, следовательно, (я-1)-различимы. Значит, существует входная последовательность длины п - 1 или менее, которая, будучи приложенной к M\ai, и Жад, вызывает различные выходные последователь-

формой И, следовательно, без потери общности предполагать, что М минимален.

ai , ai ..... ai ], одно из кото-

12 raj



4.4] ЭКСПЕРИМЕНТЫ ДЛЯ ДВУХ СОСТОЯНИЙ 127

НОСТИ. Такая входная последовательность называется диагностической последовательностью для [oi„, о/„). Диагностический эксперимент для двух состояний для автомата М при А{М) = {oi„, а;„) состоит, следовательно, в приложении к М диагностической последовательности для {а/„, OyJ и в наблюдении реакции; на основании этой реакции может быть определено истинное начальное состояние. В оставшейся части этого параграфа мы покажем, как могут быть построены диагностические последовательности для заданных пар состояний.

Пусть О/, и ау„ будут /-различимы и (I - 1)-эквива-лентны, для некоторого I, 1 / я - 1 *). Тогда длина кратчайшей диагностической последовательности для {а,„, Oj} есть /. Любая диагностическая последовательность для {Oi,, Од), длина которой равна определенному выше значению /, будет называться минимальной диагностической последовательностью для [ai,, Од) и обозначаться (а/„, О;,). Если О/, и Оу-, /-различимы и (/-1)-эквивалентны, то О/, и ау„ должны быть разобщенными состояниями в Pi и объединенными в Pi i. Поэтому / может быть определено путем построения й-эквивалентных разбиений для данного автомата М и нахождения наименьшей величины k такой, что Pj содержит ai„ и aj в двух различных классах; эта величина должна равняться /.

Когда {oi,,, Oj,) прикладывается к M\ai и M\Oj, выходные последовательности получаются одинаковыми, за исключением последнего /-го символа. Следовательно, йге преемники и Оу, относительно (0/„, а;„) являются (/ - k)-различимыми и (/-ft--эквивалентными для всех О <; ft <;/-1. Это положение изображено на рис. 4.2, где {Оц, Од) представлена в виде последовательности lulu . • • .. . ы,. Последовательности состояний, которые проходят

автоматы Жа/, и Жау„ есть соответственно О/, Oi.....Ot

и Oj, Oj.....Oj. При этом выходные последовательности

имеют вид lvv2---lt\ для автомата Жа/ и Сг/,/. . С",

) Так как 0-эквивалентпость не определена, состояния, которые 1-различимы и 0-эквивалентны, должны считаться просто 1-раз-личимыми.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [ 39 ] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]

0.0018