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

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

являются 2-эквивалентными, а разобщенные состояния являются 2-различимыми. Ни одно состояние автомата Л7 не является 2-эквивалентным состоянию 9 (за исключением самого состояния 9), и, следовательно, состояние 9 образует класс, состоящий из одного состояния, - одноэлементный класс.

(o:/rjN(pm


Рис. 3.3. Автомат А1.

Ясно, что ни одно состояние не может принадлежать одновременно двум различным -эквивалентным классам, поскольку это означало бы, что это состояние является &-раз-личимым по отношению к самому себе. Следовательно, общее число состояний в равно общему числу состояний

в автомате.

Лемма 3.5. k-эквивалентное разбиение автомата единственно.

Доказательство. Предположим, что разбиение Р, состоящее из 2*, Sft, Sft , не является единственным. Тогда для этого же автомата должно быть другое А-эквива-лентное разбиение, скажем Рк, состоящее из 2/,, ... • Пусть S4=r{ar, Ог, OrJ. Поскольку состоя-

ния из являются -эквивалентными и поскольку не



имеется ни одного состояния вне 2, являющегося эквивалентным какому-либо состоянию из 2, то в должен быть класс состояний, скажем 2,, состоящий из состояний Ог,,

Or.....и не содержащий никаких других состояний.

Предположив, что г принимает значения 1,2.....м, получим,

что каждому классу в соответствует идентичный класс в Pft. Поскольку общее число состояний в должно быть таким же, как в Р*, то Р и Р должны быть одинаковыми и, следовательно, Р является единственным.

Лемма 3.6. Состояния, являюш,иеся разобщенными в Pj, должны быть разобщенными в P+i-

Доказательство. Согласно лемме 3.4 два состояния, являющиеся /-различимыми, являются и (--1)-различимыми. Тогда - справедливость доказываемой леммы непосредственно вытекает из определения Р и P+i-

Например, Р3 автомата Л7 не может содержать такие классы, как {1, 3, 6) и {2, 5, 9}, поскольку эти классы, как следует из (3.1), содержат состояния, которые в Pj являются разобщенными.

Лемма 3.7. Если автомат М имеет два различимых, но k-эквивалентных состояния, то он также должен иметь два состояния, которые являются k-эквивалентными, но (k-\-l)-различимыми.

Доказательство. Пусть о,- и Oj будут различимыми

-эквивалентными состояниями автомата М и пусть входная

Таблица 3.2

Автомат А1





Рис. 3.4. Иллюстрация к лемме 3.7.

Предположим теперь, что смежные состояния в каждом классе эквивалентности разбиения Р/ являются эквивалентными. Тогда ясно, что Я+ц совпадает с Р,, для всех неотрицательных целых и. Если два смежных состояния в являются различимыми, то они представляют собой два различимых состояния, которые являются -эквивалентными. В этом случае, согласно лемме 3.7, автомат должен иметь

последовательность Infih • • - Ц будет наикратчайшей входной последовательностью, различающей состояния и Oj. Это значит, что О; и Оу вырабатывают различные выходные символы не раньше, чем будет приложен входной символ л. Поскольку О; и Оу являются -эквивалентными, то должно быть lyk. Пусть (/ - k - 1)-ми преемниками и Оу по отношению к входной последовательности Ih

будут al и о, соответственно; так как / > то / ~ k - 10, и эти преемники всегда существуют. Тогда и Оу могут быть различимы при входной последовательности •. •

. . . й, длина которой равна / - (/ - k - \) = k-\-\. Эти

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

лентными. Следовательно, и Оу являются -эквивалент-

пыми, но (&--1)-различимыми. Лемма доказана. Рассмотренная ситуация иллюстрируется на рис. 3.4.



[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