2.9. Матрицы переходов высшего порядка

Последовательность k дуг, которая в графе переходов ведет из одного состояния в другое, называется путем; k называется длиной пути. обозначает множество всех путей длины k, которые ведут из состояния в состояние . Множество которое состоит из одной дуги, ведущей из будем обозначать . Если пусто ( т. е. если ни одна дуга не ведет из то ему придается значение 0 (нуль).

Путь длины k, представляющий собой упорядоченную последовательность дуг (Рис. 2.9) символически изображается упорядоченным произведением

Рис. 2.9. Путь

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

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

Лемма 2.2.

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

Заменяя индекс и на и индексы на попучим:

Для автоматов с состояниями матрица переходов порядка обозначается и состоит из строк и столбцов, обозначенных так же, как и в матрице Элемент матрицы обозначается и определяется так:

Для имеем:

записывается как и может быть получена из путем замены каждого ненулевого элемента в матрице

Умножение матриц переходов высшего порядка определяется следующим образом. Если имеет элемент и если каждая из этих матриц является квадратной -матрицей переходов высшего порядка, то

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

Лемма 2.3.

Доказательство. Из (2.19), (2.20) и (2.21) следует, что элемент произведения матриц является суммой . Однако, согласно (2.16) и (2.19), это — элемент что доказывает лемму.

Теорема 2.3. Элемент матрицы является множеством всех путей длины k, ведущих из состояния в состояние в автомате М.

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

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

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

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

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