2.13. Частичное построение матриц

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

Лемма 2.8. Пусть обозначает матрицу - строку, построенную из строки матрицы . Тогда

Доказательство. Из определения Р и и преобразований, аналогичных проведенным в (2.17), получим:

Для фиксированного i множество состоит из элементов строки матрицы . Также для фиксированного I множество состоит из элементов матрицы - строки, полученной умножением на . Следовательно, равенство (2.42) выполняется.

Лемма 2.8 означает, что может быть построена путем последовательного умножения на матрицу - строку, а не на квадратную матрицу. Когда представляют интерес только пути, начинающиеся в такое частичное построение матрицы оказывается достаточным, так как [Ж содержит ту же информацию об этих путях, что и вся матрица . В результате объем преобразований над матрицами сократится примерно в число раз, равное числу строк в матрице Можно заметить, что описанная схема частичного построения непосредственно применима к построению матриц описанному в алгоритме 2.4.

Матрицы (2.44) — (2.47) иллюстрируют схему частичного построения матрицы для определения всех элементарных путей длины 1, 2, 3 и 4, начинающихся в состоянии 1 автомата обозначает строку матрицы

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