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

[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.6. Автомат Ж.

(/3/1)


Рис. 2.8. Автомат Д (Л4, Л5).



автомат Alj.....или автомат Жд,. Эта интерпретация основывается на том факте, что если Д(ж1, Жз. находится в состоянии o„, принадлежащем подавтомату Ж, то Д(ж1, Жз.....Жд,) никогда не может перейти в какое-либо состояние подавтомата Жу, где j Ф1, так как Ж; и Mj-два изолированных подавтомата. Поведение автомата

A(/VIi, ж2.....Л/д,), находящегося в состоянии о, совпадает

поэтому с поведением автомата Ж, находящегося в состоянии Оц. Следовательно, автомат Л (Жр М.....Жд,) может

быть представлен автоматом Ж или автоматом ж2.....или

автоматом Жy, в зависимости от начального состояния.

В качестве примера рис. 2.6 и таблица 2.7 представляют автомат Л4, а рис. 2.7 и таблица 2.8 - автомат А5. Расщепляемый автомат, составленный из автоматов Л4 и Л5, Л(Л4, Л5), представлен на рис. 2.8 и в таблице 2.9.

Таблица 2.7 Автомат АА

Таблица 2.8 Автомат АЪ

\ X..

V \

Таблица 2.9

Автомат Д (i44, АЪ)



etj = { (2.11)

\ О, если не существует.

Для ясности обычно обозначение k-то состояния приписывают Л-й строке и k-щ столбцу и называют их «строка о» и «столбец о» соответственно. Выражение (2.12) изображает матрицу переходов автомата А\, заданного в виде графа на рис. 2.2.

[А\] =

1 2 3 4 5

1-(я/0) (rf/0)V(n/0)V(X/0) (u/0) О О -

(я/О) (rf/0)V(n/0)V(«/0)V(V0) ООО (я/О) (rf/0)V(«/0)V(X/0) О (л/0) О .

(я/О) О О (n/0)V(«/0)V(V0) (rf/0)

5 (я/1) О О (n/0)V(«/0)V(V0) (rf/0)

(2.12)

= 3 4

) Материал, относящийся к матрицам переходов, частично базируется на работе Хона, Сешу, Ауфенкампа (F. Е. Н о h п, S. S е S h U and D. D. А U f е п к а m р. The Theory of Nets, J. R. E. Trans., vol. EC-6, pp. 154-161, 1957).

2.8. Матрица переходов О

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

Для автомата М, имеющего п состояний, матрица переходов состоит из п. строк и п. столбцов и обозначается [М]. Пусть {о;, Oj, а„)-множество состояний автомата М и пусть bij обозначает дугу графа переходов автомата М, направленную от О; к Оу. Элемент (/, у) (т. е. содержимое клетки, расположенной на пересечении /-й строки и у-го столбца матрицы [М] обозначается ej и определяется так:

I bij, если bij существует,



[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