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

[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 в любом из его состояний от автомата М.

Автоматы Ml и являются различимыми тогда и только тогда, когда имеется, по крайней мере, одно состояние в A/j, которое не является эквивалентным никакому состоянию в или если имеется, по крайней мере, одно состояние в М2, которое не является эквивалентным никакому состоянию в Mj, Эквивалентность автоматов и М2 обозначается равенством = М2, а различимость автоматов и - неравенством Ml ф М2. Пользуясь определением 3,3 легко показать, что эквивалентность автоматов обладает свойством рефлексивности (/И,- = М, свойством симметричности (если Mi=Mj, то Mj= Ml) и свойством транзитивности (если Mi= Mj и My=Mj, то Mi= М. Следовательно, эквивалентность автоматов может рассматриваться как обычное отношение эквивалентности и применяться непосредственно к множествам автоматов любой мощности. С другой стороны, различимость автоматов (а/О) не обладает свойствами реф-

лексивности и транзитивности и поэтому может относиться только к паре автоматов.

Определение эквивалентности автоматов означает, что два


(а/!)

Рис. 3.5. Автомат Л8.

(a /j Ш (a/V

Рис. 3.6. Автомат /19.

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

Автоматы Л8 и Л9, изображенные на рис. 3,5 и 3.6 соответственно, представляют собой два эквивалентных




автомата. В этом можно убедиться, если обратить внимание на то, что Л9 становится автоматом А8, если не учитывать состояние 3 автомата А8. Следовательно, состояния 1 и 2 автомата А8 эквивалентны соответственно состояниям 1 и 2 автомата Л9. Кроме того, состояния 1 и 3 автомата Л8 явно эквивалентны и, следовательно, эквивалентны; поэтому состояние 3 А8 эквивалентно со-стоянию 1 А9. Таким образом, для каждого состояния А8 мы находим эквивалентное состояние Л9 и для каждого состояния Л9 находим эквивалентное состояние Л8. Это означает, что Л8 и Л9 являются эк-Рис. 3.7. Автомат Л10. вивалентными автоматами.

Сравнивая автомат Л9 с автоматом Л10, изображенным на рис. 3.7, можно заметить, что Л9 становится одинаковым с Л10, если не учитывать состояние 3 Л10; следовательно, для каждого состояния Л9 мы находим эквивалентное состояние Л10. Однако, поскольку пары состояний {1, 3} и {2, 3} являются явно различимыми и, следовательно, различимыми, утверждение, обратное последнему, не верно. Поэтому Л9 и Л10 не являются эквивалентными.

3.10. Эквивалентное разбиение множеств автоматов

Эквивалентное разбиение автомата, состоящего из множества автоматов 9№={M], Mj, МдЬ представляет собой разбиение Ш на классы таким образом, что два автомата принадлежат одному и тому же классу тогда и только тогда, когда они являются эквивалентными. Каждый класс автоматов в этом разбиении называется классом эквивалентных автоматов. Очевидно, что автоматы не могут быть эквивалентными, если они несравнимы. Следовательно, до разбиения на классы эквивалентных автоматов множество Ш следует сначала разбить на подмножества таким образом, чтобы два автомата относились к одному и тому же подмножеству тогда и только тогда, когда они сравнимы. Впоследствии каждое подмножество может индивидуально подвергаться



дальнейшему разбиению. Поскольку разбиение множества автоматов в соответствии с их входным алфавитом является тривиальной задачей, то потеря обш,ности будет незначительной, если мы предположим, что все автоматы в Ш сравнимы. При таком допущении можно построить расщепляемый

автомат .....М/у) так, как было описано в § 2.7.

Разбиение автомата {М, М.2.....М) на обычные

кла.сы эквивалентности любым из описанных в §§ 3.6-3.8 способов, выявляет, являются ли любые два автомата /И,-и Mj из множества ЗК эквивалентными. Действительно, по определению 3.3, М и Mj являются эквивалентными, если каждый класс эквивалентности, который содержит состояние автомата Ж;, также содержит состояние автомата Mj и если каждый класс эквивалентности, который содержит состояние автомата Mj содержит также состояние автомата М; в противном случае Ж,- и Mj являются различимыми. Когда определены все пары эквивалентных автоматов из множества Ш, эквивалентное разбиение автоматов из 9й может быть произведено с помощью алгоритма, аналогичного алгоритму 3.1 (в котором теперь рассматриваются не состояния, а автоматы).

В случаях, когда число автоматов N велико, определение классов эквивалентности автоматов облегчается построением так называемой таблицы эквивалентности для расщепляемого автомата .{М, М.....Жу). Эта таблица имеет строку

для каждого класса эквивалентности автомата ДСЖ;, М, •. ., Ждг) и столбец для каждого автомата Ж, из множества Ш. Общий вид таблицы эквивалентности показан в таблице 3.11. Клетки таблицы эквивалентности заполняются в соответствии со следующим правилом: в клетке, где пересекаются строка {0л , Ол.....OftrJ и столбец Ж,-, ставится 1, если какое-нибудь состоян le в классе эквивалентности 0ft, .....Олл принадлежит автомату Ж,, и О -

в противном случае. Таким образом, Ж; и Mj являются эквивалентными тогда и только тогда, когда столбцы Ж; тл Mj являются одинаковыми во всех строках таблицы эквивалентности. Поэтому эквивалентное разбиение автоматов приводит к разбиению столбцов таблицы эквивалентности на подмножества таким образом, что два столбца принадлежат одному и тому же подмножеству в том и только в том



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