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

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

5.5] СИЛЬНОСВЯЗНЫЕ АВТОМАТЫ 197

лированный подавтомат, не может быть сильногвязным автоматом. Таким образом, сильносвязным является такой автомат, в котором можно перейти в каждое состояние независимо от предыстории автомата.

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

Лемма 5.1. Если автоматы и AIj являются сильносвязными и различимыми, то ни одно состояние в Ml не эквивалентно какому-либо состоянию в М2.

Доказательство. Пусть множеством состояний автомата Ml будет множество (Oj, .....о}, а множеством

состояний автомата М-\а[, а.....oJ. Предположим,

что в автомате Mi имеется состояние а,-, которое эквивалентно некоторому состоянию а, в М. Пусть будет

входной последовательностью, которая переводит автомат Mi из состояния О; в Ol, а - входной последовательностью, переводящей автомат Mi из состояния a, i в состояние для k = 2, 3.....n-i (все такие последовательности существуют, поскольку автомат Mi сильносвязный). Приложим последовательность 12 ••• п, ili г]"/* После приложения последовательности 12 • • 1 окажется в состоянии а, а М - в некотором состоянии aj . Так как

= aj, то их преемники по отношению к любой входной последовательности должны быть эквивалентными, следовательно, о = о. для k = 2, 3.....rii. Таким образом, для

каждого состояния в Mi существует эквивалентное состояние в М2. Теперь пусть i будет входной последовательностью, которая переводит автомат М2 из состояния aj в а[, а - входной последовательностью, которая переводит М

из состояния a j в для /г = 2, 3.....«2 (< такие

последовательности существуют, так как М2 - сильносвязный автомат). Приложим последовательность 12 • • • к i0/



И К После приложения • • • k 2 окажется в

состоянии Oj, а - в некотором состоянии а,. Поскольку = а\, то мы должны получить, как и прежде, =

для k=l, 2.....П2, то есть для каждого состояния в М2

существует эквивалентное состояние в М. Таким образом показано, что если а, = aj, то = М2. Это противоречит условию теоремы и, следовательно, ни одно состояние в Mi не может быть эквивалентным какому-либо состоянию в Alj-

Теорема 5.6. Если M=[Mi, М2.....Л1д,) является

конечным классом сильносвязных автоматов таких, что среди них никакие два автомата не являются эквивалентными, то класс Ш является исключительным.

Доказательство. Предположим, что Ш не является исключительным классом. Тогда в некотором автомате М должно существовать состояние, эквивалентное некоторому состоянию в другом автомате Mj (у Ф i). Однако, согласно лемме 5.1, это невозможно, поскольку М и Mj различимы и сильносвязны. Полученное противоречие доказывает, что класс Ш должен быть исключительным.

Объединяя теоремы 5,3 и 5.6, получим

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

5.6. Некоторые свойства сильносвязнь1х автоматов

Обратимым автоматом называется автомат, который всегда возможно установить в начальное состояние. Ясно, что каждый сильносвязный автомат является обратимым. Обратное утверждение, однако, неправильно: обратимый автомат не обязательно сильносвязный.

Теорема 5.7. Автомат, в котором каждый изолированный подавтомат является сильносвязным, является обратимым.

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



5.6] НЕКОТОРЫЕ СВОЙСТВА СИЛЬНОСВЯЗНЫХ АВТОМАТОВ 199

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

Теорема 5.8. Обратимый автомат является сильносвязным тогда и только тогда, когда он не содержит изолированных подавтоматов.

Доказательство. Ясно, что если обратимый автомат состоит из двух и более изолированных подавтоматов, то он не может быть сильносвязным. Теперь предположим, что обратимый автомат М не содержит изолированных подавтоматов, но содержит преходящий (а значит, и тупиковый) подавтомат. Это означает, что в автомате М может быть начальное состояние, в которое нельзя вернуться, и, следовательно, что автомат М не является обратимым. Тогда из полученного противоречия следует, что автомат М не может включать в себя преходящих тупиковых подавтоматов. Так как автомат является сильносвязным тогда, когда он не содержит преходящих, тупиковых, изолированных подавтоматов, то, следовательно, если обратимый автомат не содержит изолированных подавтоматов, он должен быть сильносвязным.

Важным свойством сильносвязного автомата является то, что он всегда может быть установлен в любое заданное конечное состояние.

Теорема 5.9. Пусть М является сильносвязным автоматом с п состояниями. Тогда он может быть установлен в любое заданное состояние простым условным экспериментом длины I и порядка d, где

/<4(« + 2)(«-1). (5.8)

rf<«. (5.9)

Доказательство. Используя выражения (4.23) и (4.24), автомат М всегда можно перевести в известное (но не обязательно заданное) конечное состояние простым условным экспериментом длины п(п- 1)/2 или менее и порядка п- 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.0009