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

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

Тогда матрица может быть построена из или посредством замены каждого ненулевого элемента в этих матрицах на 1. Теорема 2.5. Элемент матрицы где равен числу путей длины k, ведущих из состояния в состояние в автомате М.

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

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

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

    (2.37)

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

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

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

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

При таком определении матрица может быть построена из заменой каждого ненулевого элемента в числом пар вход - выход, содержащихся в этом элементе. Матрицу можно рассматривать как скелетную матрицу автомата где каждая дуга, обозначенная h парами вход - выход, заменена h параллельными дугами, каждая из которых обозначена одной парой вход - выход. Благодаря такой замене число дуг, содержащихся в каком-либо пути, становится равным числу пар вход - выход, содержащихся в обозначениях всех дуг этого пути. Таким образом, элемент (i, j) матрицы должен совпадать с общим числом входных последовательностей длины k, которые переводят М из

Матрицы (2.40) и (2.41) иллюстрируют построение модифицированной скелетной матрицы автомата (рис. 2.2) и построение по этой матрице матрицы второй степени. Из видно, например, что имеются три кратчайшие входные последовательности, которые переводят из состояния 4 в состояние 2, и что есть 12 входных последовательностей длины 2, которые переводят из состояния 5 в состояние 4.