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

[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.13, в которой для автомата Л17, показанного на рис. 4.3, и множества допустимых начальных состояний {1, 2, 3, 4, 5} построен регулярный безусловный установочный эксперимент.

Таблица 4.13

Регулярный безусловный эксперимент для Л17 и множества допустимых начальных состояний {1, 2, 3, 4, 5}

{1, 2, 3, 4. 5}

{1. 1,5}, {3, 2}

{1. 1}, {2}. {5, 1}

{1. 1}. {1}. {2}, {1}

Oq представляет собой множество (1, 2, 3, 4, 5}, а для kl строится на основе О-ь т. е. на основе предварительно определенной подпоследовательности (подпоследовательности, приведенной в последнем столбце строки k-1) и таблицы или графа переходов для Л17. Пара состояний (Oj, Оу} есть любая пара состояний в любом однородном 0-множестве, содержащемся в 0; (о, aj) есть минимальная диагностическая последовательность для (а, Оу), которая может быть получена по методу, описанному в § 4.4. Для того чтобы минимизировать длину индивидуальных подпоследовательностей, О; и Оу можно выбрать так, чтобы они давали в результате кратчайшее (о,, Оу). Для автомата Л17 это может быть выполнено с помощью таблицы 4.6, в которой приводится перечень минимальных диагностических последовательностей для всех пар состояний в Л17. Следует отметить, что, вообще говоря, это правило выбора не гарантирует минимальности общей длины установочного эксперимента (хотя в нашем примере оказалось, что результирующая установочная последовательность является минимальной). Строка 3 в таблице - последняя, так как О3 является однородной Л-группой. Установочная последовательность строится



путем выписывания последовательностей (о,-, -Oj) в порядке, в котором они появляются в последнем столбце. Поэтому регулярный установочный эксперимент для Л17 и множества допустимых начальных состояний (1, 2, 3, 4, 5} состоит в подаче ааа и наблюдении реакции. Реакция состояний 1, 2, 3, 4 и 5 на ааа и соответствующее конечное состояние показаны в таблице 4.11.

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

4.16. Регулярные условные установочные эксперименты

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

трений.

Алгоритм 4.8. Даны автомат М и его множество допустимых начальных состояний А{М)\ требуется определить конечное состояние М с помощью простого условного эксперимента. (1) Пусть А{М) есть g. Полагаем /г = 0. (2) (а) Если g, неоднородно, то определяем регулярную подпоследовательность, скажем для g,. Прилагаем

к Ж и полагаем, что g является подмножеством g.



которому может быть свойственна наблюдаемая реакция. Пусть ft+iCTb -преемник g-. Увеличиваем/г на 1 и возвращаемся к (2). (б) Если gi, однородно, то конечное состояние М есть состояние, содержащееся в g/,.

Если g;, в алгоритме 4.8 не является однородным, то мощность g/i+i должна быть меньше, чем мощность g. Следовательно, если мощность А(М) есть т, то число подпоследовательностей не превышает т - 1. Для g/ мощности г всегда имеется регулярная подпоследовательность j,, длина которой не превышает п-r-j-l, где п есть общее число состояний в М. Следовательно, общая длина установочного эксперимента не может превосходить

2(А-л+1)=1(2л-/я)(/«-1).

г = 2

(4.14)

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

Теорема 4.13. Установочная задача для автомата с п состояниями и т допустимыми состояниями может быть всегда решена с помощью простого условного эксперимента длины I и порядка d, где

1±(2п~т)(т - 1), d<m -1.

(4.15) (4.16)

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

Таблица 4.14

Регулярный условный эксперимент для Л17 и множества допустимых начальных состояний {1, 2, 3, 4, 5}

Истинное состояние

«*

"1 "j

§ (0.. Oj)

Реакция

{1. 2, 3, 4, 5}

{3. 2}



[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.0008