|
|
|
Главная Кибернетика [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] I, 3, 5, 7 И 8 И строк (и столбцов) 2, 4, 6 и 9, при этом группы разделяются пунктирной линией. Матрицей [Л7]<", полученной в результате этих операций, является матрица (3.11). Построение матрицы [Mf по [Ж]**(ft > 1). Пусть о,- и Oj - две строки в одной и той же группе строк [/И](*П Если в каждой из подматриц, пересеченных строками и Oj, строки и Oj имеют одинаковые множества пар вход-выход, то О; и Оу представляют собой ft-эквивалентные состояния, первые преемники которых по отношению к любому входному символу являются ft-эквивалентными, поэтому состояния Oi и Оу являются (ft--1)-эквивалентными. Если эти условия не имеют места, то и Оу являются (ft--1)-различимыми. Таким образом, матрица [Ж]**"*" может быть построена по [Ж]**, если разделить каждую группу строк в [Ж]** на подгруппы так, чтобы две строки принадлежали одной и той же подгруппе тогда и только тогда, когда они имеют одинаковые пары вход-выход в каждой из пересекаемых ими подматриц г. Каждая такая группа представляет собой (ft--1)-эквивалентный класс. Произведя симметрическую перестановку и симметрическое разбиение матрицы [Ж]**, получим в результате [Ж]**"*"". Например, строки 1, 3, 5, 7 и 8 в [Л7]*1 имеют одинаковые множества пар вход-выход в каждой подматрице, которую они пересекают. С другой стороны, строки 2, 4 и 6 образуют в пересекаемых подматрицах множества пар вход-выход, которые отличаются от множества пар вход-выход, образованного строкой 9. Следовательно, строки 2, 4 и б и строка 9 дают две различные группы в [Л?], как показано в (3.12). Матрица [Ж]* дает эквивалентное разбиение тогда, когда никакое дальнейшее разбиение не может быть произведено (т. е. когда каждая подматрица имеет одну строку и один столбец или когда строки внутри каждой подматрицы имеют одинаковые множества пар вход-выход). При этих условиях различные группы строк (или столбцов) являются классами ft-эквивалентности, где ft может быть сделано сколь угодно большим; поэтому эти группы представляют собой классы эквивалентности автомата Ж. Согласно теореме 3.5, это может иметь место для некоторого значения kn- I. [Л7] = (а/О) О О О О О (а/1) V (Р/О) О (а/1) V (Р/О) (Р/1) V (Y/I) О (Р/О) о о о (а/О) (Y/0) (Р/1) V(Y/1) О О (Р/О) О О (а/1) V (Р/О) О (Y/0) О (Y/0) О (а/1) (Y/I) (а/1) о о о (Y/0) (а/О) (Y/0) О (а/О) V (Y/1) О [Л7](>) I 3 5 О О (Y/0) О О (Y/0) О (Y/0) О О О О (Y/0) О О О (V/0) (а/1) V (Р/0) (а/1) V (Р/0) О (Р/0) О (Р/0) (а/1) О (а/1) (а/О) V (Р/О) О (р/1) о о (Р/1) (3.10) 2 (а/О) 0 0 О 0.0 (Р/1) V (Y/I) О О 4 О (а/Й ООО (Р/1) V (Y/I) О 00 ООО О (а/О) О О (Y/I) (Р/1) О О О (а/О) V (Y/1) 0 0 0 0 (Р/1) (3.11) Матрицы (3.10)-(3.14) иллюстрируют описываемый метод эквивалентного разбиения автомата А7. Матрица [Л7]<> дальнейшее разбиение которой невозможно, очевидно, содержит эквивалентное разбиение {1, 3, 8}, {2, 4}, {5, 7], {6} и (9), совпадающее с разбиением (3.9). [Л7](2) =
(3.12) [Л7](3) =
[/4 ?](<) = I (3.13)
(3.14) 3.9. Эквивалентность автоматов Понятие эквивалентности можно распространить на весь автомат с помощью следующих определений: Определение 3.3. Говорят, что автомат Mi и автомат М2 эквивалентны, если каждому состоянию автомата Ml соответствует, по крайней мере, одно эквивалентное ему состояние в автомате и если каждому состоянию Oj автомата М соответствует, по крайней мере, одно эквивалентное ему состояние в автомате Mi Если автоматы Mi и М2 не эквивалентны, то они различимы. Таким образом, Mj и М2 являются эквивалентными тогда и только тогда, когда, наблюдая сигналы на их выходах. [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 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||