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

[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.12) СКЕЛЕТНАЯ МАТРИЦА б5

2.12. Скелетная матрица

В ряде задач детальное знание элементов матрицы высшего порядка несущественно, и решение может быть получено при изучении степеней так называемой скелетной матрицы, отличающейся тем, что она имеет существенно более простые элементы. Для автомата Men состояниями скелетная матрица составляется из п строк и я столбцов, обозначаемых так же, как в [М], и обозначается [М]. Элемент (г. У) матрицы [М] обозначается Cij. Если обозначает дугу, ведущую из состояния в состояние Oj в автомате М, то определяются так:

1 1, если существует,

\ О, если bij не существует. (2-34)

Тогда матрица [М] может быть построена из [М] или [М] посредством замены каждого ненулевого элемента в этих матрицах на 1.

Теорема 2.5. Элемент {I, j) матрацы [Ж]*, где

k = \, 2..... равен числу путей длины k, ведущих из

состояния О; в состояние Oj в автомате М.

Доказательство. Для Л==1 теорема справедлива по построению. Предположим, что теорема справедлива для к; тогда элемент (и, J) матрицы [Ж]*, обозначаемый е*], представляет число путей длины k, ведущих из o„ в Oj. Элемент (/. У) матрицы [Ж] [Ж]*= [Ж]*"* определяется формулой

1*-+"= (2.35)

в выражении (2.35) умножается на 1. если в o„ можно попасть из О;, пройдя только одну дугу, и умножается на нуль в противном случае. Следовательно, элемент е(.*.+ > равен числу путей длины ведущих из о, в О;. По



[Л11 =

И1Р = :

[Alf = :

"1

0"

"8

1"

(2.36)

(2.37)

(2.38)

Сжатая цифровая форма скелетной матрицы может быть использована в задачах, где важно знать наличие или число путей между определенными состояниями, но не обязательно знать, какие дуги входят в каждый путь. Можно определить число минимальных путей, ведущих из в Oj, посредством построения [Mf для последовательных значений kn-1; если элемент (/, у) равен нулю в но не равен нулю

в [Ж]*, то элемент (/, J) матрицы [Mf представляет собой число минимальных путей длины к; если элемент (г, у) равен нулю в [М]"~, то путь между и Оу не существует.

Матрицы (2.36) - (2.38) иллюстрируют построение скелетной матрицы для автомата Л1, изображенного на рис. 2.2,

индукции теорема верна для всех Л > 0.



{ЧИ( 0.

(2.39)

2,12] СКЕЛЕТНАЯ МАТРИЦА 67

И построение по этой матрице матриц второй и третьей

степени. Из [А1] видно, например, что в состояние 5 нельзя попасть из состояния 2 ни одним путем, имеющим длину меньше 4, и что в состояние 1 можно попасть из состояния 4 девятью различными путями длины 3.

Следует заметить, что, поскольку одна дуга может соответствовать более чем одной паре вход-выход, то ненулевой элемент (1, матрицы [М]* не обязательно представляет число всех входных последовательностей длины к, которые переводят автомат М из состояния в Оу, -Если представляет интерес число входных последовательностей, переводящих Ж из О; в Оу, а не число путей, то можно определить модифицированную скелетную матрицу, обозначаемую через \М\, элемент (/, /) которой, обозначаемый еу, определяется так:

числу пар вход-выход, обозначающих дугу bij, если bij не существует.

При таком определении матрица \М\ может быть построена из \М] заменой каждого ненулевого элемента в [М] числом пар вход-выход, содержащихся в этом элементе. Матрицу \М\ можно рассматривать как скелетную матрицу автомата М, где каждая дуга, обозначенная h парами вход-выход, заменена h параллельными дугами, каждая из которых обозначена одной парой вход-выход. Благодаря такой замене число дуг, содержащихся в каком-либо пути, становится равным числу пар вход-выход, содержащихся в обозначениях всех дуг этого пути. Таким образом, элемент (/, /) матрицы [Ж]* должен совпадать с общим числом входных последовательностей длины к, которые переводят Ж из в Оу.

Матрицы (2.40) и (2.41) иллюстрируют построение модифицированной скелетной матрицы автомата А\ (рис. 2.2) и построение по этой матрице матрицы второй степени. Из

[Л1р видно, например, что имеются три кратчайшие входные последовательности, которые переводят А\ из состояния 4 в состояние 2, и что есть 12 входных последовательностей длины 2, которые переводят А\ из состояния 5 в состояние 4.

б»



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