где нулевые компоненты интерпретируются как несуществующие пути.

Лемма 2.2.

11 tuPlj- (2-16)

u= 1

Доказательство. Применяя (2.15), получим:

п п ( п п п \

ляп п

= 2 S Д 2 Я, , . . . Я, ,;. (2.17)

U-1 1,-1 1-1 !--

Заменяя индекс и на и индексы h - l, 2.....k - 1,

на l/j-y, попучим:

i: muPi)=i: i:... i я„ я,,,... л,,=р,7 (2.18)

Для автоматов с п. состояниями матрица переходов k-го порядка обозначается [Ж]** и состоит из п строк и п столбцов, обозначенных так же, как и в матрице [Ж]. Элемент (/, у) матрицы [Ж]** обозначается efj и определяется так:

ef] = Pf]. (2.19)

Для k - 1 имеем:

el] = Pl] = nij. (2.20)

[Ж]*! записывается как [Ж] и может быть, получена из [Ж] путем замены каждого ненулевого элемента (/, у) в матрице [Ж] на я,.

Умножение матриц переходов высшего порядка определяется следующим образом. Если [А] имеет элемент (/, J), равный jiij, [В] - элемент (/. у), равный bj, и [С] = = [Л] [fi]-элемент (/, у), равный су, и если каждая из этих матриц является квадратной (л X л)-матрицей переходов высшего порядка, то

Cija,Jy,j. (2.21)

Ц»1

) Такие произведения в дальнейшем называются членами элементов матрицы. {Прим. перев.)

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

Лемма 2.3.

[Mf+ = [M][MfK (2.22)

Доказательство. Из (2.19), (2.20) и (2.21) следует, что-элемент (/, у) произведения матриц [М] [Ж]* является сум-

мой niuPuj- Однако, согласно (2.16) и (2.19), это-эле-

u = l

мент е*у+, что доказывает лемму.

Теорема 2.3. Элемент {I, J) матрицы [Ж]*, k =

= 1, 2.....является множеством всех путей длины k,

ведущих из состояния в состояние Оу в автомате Ж.

Доказательство. Теорема эквивалентна утверждению, что [Ж]* = [Ж]*. Для k = \ это равенство справедливо по построению. Если равенство справедливо для k = h, то из (2.22) получаем:

[Mf+ = [Ж] [Ж]*" = [Ж] [М]" = [Mf- (2.23)

По индукции следует, что указанное равенство справедливо для любого kl.

Теорема 2.3 показывает, что множество всех путей длины k, ведущих из одного состояния в другое, может быть построено систематически путем возведения матрицы [Ж] в k-ю степень. Нижние индексы содержащихся в матрице путей соответствуют дугам, из которых составлены эти пути. Обращаясь к графу или матрице переходов, можно определить обозначения этих дуг, а следовательно, и соответствующие путям входные и выходные последовательности.

Например, (2.24) является матрицей переходов первого, а (2.25)-матрицей переходов второго порядка автомата А1,

заданного матрицей переходов (2.12). Из (2.25) видно, в частности, что имеются два пути длиной 2 из состояния 3 в состояние 2, а именно n3jni2 и Пз2л:22> " пути длиной 2 из состояния 2 в состояние 4 или 5. Из (2.25) и (2.12) также можно заключить, что в состояние 2 можно попасть из состояния 5, если подавать входные последовательности nd, или ЯП, или лк.

1 2 3 4 5

[лГ1 = з

Я21 Я22 о

Яз1 Я32 о

Я41 О О

Я51 о о

55-.

(2,24)

[1Т]2 = 3 4

+ "121 + "13% Я21Я„ -- Я22Л21

3111 Ч~ 3221 + 34-41 Я41Я11 + Я44Я41 + Я45Я51

5 Л51Я11 + Я54Я41 -(- Я55Я51

Я11Я13 Я21Я13

Яз]Я1з

Я41Я13

5113 П54Я44 + Я55Я54 Я54Я45 + Я55Я55

Я13Я34

Я34Я44

Л„Я12 -Ь Я12Я22 + Я13Я32 2112 ~\~ 2222 3112 + 2222

Я41Я12

Я51Я12

Я34Я45 . (2.25)

Л44Я44 + Я45Я54 Я44Я45 -f Я45Я55

2.10. Элементарные пути

Путь я,[Я,, ... л, у, ведущий из в Оу, называется алементарным путем (длины k), если индексы /, I2.....j различны. Он называется элементарным контуром (длины k), если индексы /, 1, 1.....l-x различны,

а I - j. Таким образом, элементарный путь (элементарный