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

[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]

вообще говоря, нет способа сознательно восстановить началь ное состояние для того, чтобы провести новый эксперимент когда оказалось, что предыдущий эксперимент неудачен Таким образом, при проведении простых экспериментов по лезная информация, которую дает неудающийся эксперимент никогда не может быть использована для проведения даль нейших экспериментов, так как в то время, когда информа ция становится доступной, начальное состояние больше нельзя распознать. Если имеется достаточное число экземпляров данной машины, то можно провести ряд экспериментов, каждый из которых сам по себе недостаточен для того, чтобы решить диагностическую задачу, но в совокупности они дают достаточную информацию для того, чтобы распознать начальное состояние. Например, мы пришли к заключению, что нет простого эксперимента, который решает диагностическую задачу для автомата Л21, представленного на рис. 4.10, и множества допустимых начальных состояний {5, 6, 7, 8). Однако если имеются два экземпляра Л21, то решение может быть достигнуто следующим образом. Приложим аа к первому экземпляру Л21 и р - ко второму экземпляру. Если реакция первого экземпляра есть 01, то начальное состояние есть 8; если реакция есть 10, то начальное состояние есть 7; если реакция есть 00, то начальное состояние есть либо 5, либо 6. В последнем случае реакция второго экземпляра есть О, если начальное состояние есть 5, и 1, если начальное состояние - 6. Таким образом, диагностическая задача для Л21 и множества допустимых начальных состояний {5, 6, 7, 8} может быть решена кратным экспериментом кратности 2 и длины 3.

В данном месте полезно представить следующую теорему.

Теорема 4.7. В минимальном автомате с п состояниями любое множество г состояний (2 г < я) содержит, по меньшей мере, два состояния, которые являются {п - г-\-\)-различимыми.

Доказательство. По лемме 3.9, число состояний в каждом классе минимального автомата с п состояниями не превышает п - k. Следовательно, число состояний в каждом классе P„ r+i не превышает л - (я - /--(-1) = = г - 1. Следовательно, по меньшей мере, два состояния в множестве г состояний должны находиться в двух различ-



) Терминология, которая будет использована для дерева кратного эксперимента, такая же, как терминология, использованная для диагностического дерева.

НЫХ классах Р„-г+\ следовательно, являются .(я - 1)-различимыми.

Пусть для автомата М и множества допустимых начальных состояний А (УИ) мощности т. 0 является Л-группой,

состоящей из о-множеств g-j, g.....S/iu- состоит

из простого о-множества gQi, где о1 = Л(7И). O+j построено из 0 в соответствии со следующими правилами. Если g,ii имеет мощность /-2, то оно должно содержать, по меньшей мере, два состояния, скажем, Оу и о,, которые являются (я - /•-(-1)-различимыми. Разобьем g/i на такие подмножества, что два состояния принадлежат одному и тому же подмножеству тогда и только тогда, когда они дают одинаковые реакции на (Оу, О;), т. е. на минимальную диагностическую последовательность для {оу, О;). Реакция на (Оу, О;) тех состояний, которые принадлежат данному подмножеству, называется характеристической реакцией этого подмножества по отношению к (Оу, О;). о-множества 0.; являются одноэлементными в 0 и во всех подмножествах, полученных по предыдущему правилу. Если g,ii не является одноэлементным, то оно всегда может быть разбито, по крайней мере, на два подмножества, так как реакции Оу и О; на (Оу, О;) являются различными. Таким образом, если только 0 не является простым, то Oj всегда представляет собой собственное разделение 0. Так как мощность Л (УИ) есть т, то 0,„ [ должно быть простым.

Описанный выше процесс может быть показан на структуре, называемой деревом кратного эксперимента, определяемой для УИ и Л (УИ) 1). В этом дереве каждая ветвь /г-го уровня представляет некоторое g/i, а начальная ветвь представляет gQi. Ветвь, представляющая простое g,., являетсяоконечной. Если g,. не является простым и может быть разбито, скажем, на h подмножеств (способом, описанным в предыдущем абзаце), то ветвь, представляющая это g/i, расщепляется на h ветвей следующего уровня, который представляет h подмножеств, получающихся в процессе разбиения. Используя эти правила, можно развернуть все дерево



путем построения k-ro уровня на основе построенного {k-1)-го уровня. Так как множества g-,, представленные на k-u уровне, являются о-множествами 0, то отсюда следует, что высота дерева не может превышать т-1. К тому же дерево должно давать в точности т оконечных ветвей - по одному на каждое допустимое состояние.

Для наглядности все ветви в дереве сложного эксперимента, за исключением оконечных ветвей, изображаются

ffa,=U.2.J.4,5)

ff„ = {/,2,3} Sr/JJ=aa

2 ffr=<l2>

00 \ О/

8(4.5J=aaa

АГ7,

1/гг-{3) ffj-W ffziiS)

Г/оГ\ 7700

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

в форме двухполюсных блоков, представляющих экземпляры заданного автомата. Каждая ветвь снабжается обозначением представляемого ею gi. Если gi не является однородным, ветвь также обозначается последовательностью (Оу, о,), примененной при разбиении gi, и характеристической реакцией gfi по отношению к диагностической последовательности, соответствующей предыдущей ветви.

В качестве примера на рис. 4.13 показано дерево кратного эксперимента для автомата Л17 (рис. 4.3) и множества допустимых начальных состояний {1, 2, 3, 4, 5). Начальная ветвь представляет goi={l> 2, 3, 4, 5), которое есть заданное множество допустимых начальных состояний. Парой



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