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

[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) =

(Y/0)

(а/1) V (Р/0)

(Y/0)

(а/1) V (Р/0)

(Y/0)

(Р/0)

(а/1)

(Y/0)

(Р/0)

(а/1)

(Y/0)

(а/1) V (Р/0)

(а/О)

(Р/1) V (Y/1)

(а/О)

(Р/1). V (Y/I)

(а/О)

(Y/I)

(Р/1)

(а/О) V (Y/I)

(Р/1)

(3.12)



[Л7](3) =

(YO)

(a/I) V (P/O)

0 -

(Y/0)

(a/1) V (P/0)

(Y/0)

(P/O)

(a/I)

(Y/0)

(P/O)

(a/I)

(Y/0)

(a/1) V (P/O)

(а/О)

: 0

(P/I) V (Y/1)

(а/О)

(P/1) V (Y/I)

(а/О)

(Y/1)

(P/I)

(а/О) V (Y/I)

1 0

(P/1)

[/4 ?](<) = I

(3.13)

(a/I) V (P/0)

(Y/0)

(a/I) V (P/0)

(Y/0)

(a/1) V (P/0)

(Y/0)

(a/0)

(P/I) V (Y/1)

(аЮ)

(P/I) V (Y/I)

(Y/0)

(P/0)

(a/1)

(Y/0)

(P/0)

0 i (a/I)

(a/0)

(Y/I)

(P/1)

1 0

(a/0) V (Y/I)

(P/I)

(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.001