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

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

два состояния, которые являются -эквивалентными, но (k -\- 1)-различимыми. Следовательно, Р,, должно содержать два смежных состояния, которые становятся разобщенными в P + i-Таким образом, если смежные состояния в каком-нибудь классе из являются различимыми, то разбиение Р,; должно отличаться от разбиения Р. Если Р отличается от Pj, то, согласно лемме 3.6, должно существовать «собственное разделение» Р, которое должно получаться расщеплением одного или нескольких классов Р на два или более подклассов. В заключение можно утверждать следующее.

Теорема 3.4. P,,i должно быть собственным разделением Pj, если не во всех классах Р смежные состояния являются эквивалентными. В противном случае Р и Р 1,1 совпадают.

Для автомата Л7, например, имеем:

Рз: 1з,= {1, 3, 5, 7, 8}. 2з2={2. 4},

2зз={бЬ

2з4={9}.

которое является собственным разделением Рз, и

Р,: S4.= {1. 3, 8}, 242= {2, 4},

43= {5, 7}, (3.3)

244= {6}. 245= {9}.

которое является собственным разделением Р3. Однако видно, что

Р,: 251= {1. 3. 8}, 252= {2. 4}.

253= {5. 7}, (3.4)

254= {6}. 25= {9}

совпадает с Р4 и, следовательно, смежные состояния в каждом классе Р4 являются эквивалентными.



3.5. Эквивалентные разбиения

-эквивалентное разбиение автомата М называется эквивалентным разбиением М и обозначается Р, если во всех классах этого разбиения смежные состояния эквивалентны. При этих условиях каждый класс разбиения называется классом эквивалентности. Из материалов § 3.4 следует, что Р является наиболее детальным разбиением Р. По теореме 3.4, эквивалентное разбиение Р может быть получено, если образовывать Р для k=l, 2, 3 ... до тех пор, пока первый раз получится разбиение, которое совпадает с предыдущим разбиением. Это разбиение и будет Р. Пусть равенство Pi = Pj означает, что и Pj являются одинаковыми разбиениями, и пусть обозначает число классов в Р. Используя это обозначение, предыдущие результаты могут быть обобщены следующим образом:

l*l<l*+il- (3.5)

Если Pft=Pft + i, ТО

Pk = Pk,a = P ~ и = 0, 1, 2. ... (3.6)

Если все п состояний автомата являются 1-эквивалентными, то разбиение Р, состоит из одного класса, содержащего п состояний. Очевидно, что если все п состояний являются 1-эквивалентными, то их первые преемники по отношению к любой входной последовательности являются также 1-эквивалентными. Таким образом, все л состояний должны быть 2-эквивалентными и, следовательно, Pj = P2. Тогда, по (3.6), Pj = Р и все л состояний являются эквивалентными. Для автомата такого типа Д (х, s) является одинаковой для всех и, следовательно, /(л:, s = f{x. Тогда по определению, введенному в § 1.6, можно утверждать, что автомат, в котором все состояния эквивалентны, является тривиальным автоматом. В дальнейшем, если не будет специально оговорено, будут рассматриваться только нетривиальные автоматы, т. е. автоматы, в которых имеется, по крайней мере, одна различимая пара состояний или в 1-эквивалентных разбиениях которых имеется, по крайней мере, два класса.



Лемма 3.8. Если PitPk~\< "

\Pn\>k-\. (3.7)

Доказательство. Если РфРц-ъ то, по (3.5) и (3.6),

\Рг\>\Рг-\\ для г=\, 2.....к. Поскольку Р,>2.

то (3.7) следует по индукции.

Лемма 3.9. Если для автомата с п состояниями Рк-1 число состояний в каждом классе разбиения не превышает п - к.

Доказательство. Согласно лемме 3.8, число классов в Pj равно, по крайней мере, к-\-\. Предположим, что один класс содержит больше чем п - к, скажем п - к-\-\ состояний. Тогда, поскольку каждый другой класс в Р должен содержать, по крайней мере, одно состояние, общее число состояний в Pj будет не менее А + (л - к-\-\) = п-\-\. Лемма доказана, так как общее число состояний не может превосходить п.

Л е м ы а 3.10. Для автомата с п состояниями Р„ = P„ i.

Доказательство. Если Р„ Ф Рп-ь то, согласно лемме 3.8, Р„>-л--1. Так как число классов в -эквивалентном разбиении автомата с п состояниями не может превышать л, то полученное противоречие доказывает лемму.

Из леммы 3.10 и уравнения (3.6) можно вывести следующее заключение:

Теорема 3.5. Для автомата с л состояниями

Рп-х = Р- (3.8)

Таким образом, процесс определения Р для автомата с л состояниями путем последовательного построения Р для к=\, 2, 3 требует не более л-1 построений.

Другим вариантом формулировки теоремы 3.5 является

Следствие 3.1. Два состояния автомата с л состояниями эквивалентны, если они (л - 1)-эквивалентны, и различимы, если они (л-1)-различимы.

Определение Р]. Р, может быть определено с помощью следующего правила: состояния являются смежными в Pj тогда и только тогда, когда они для каждого входного символа дают одинаковые выходные символы.

Определение Р по Pi{k 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