2.10] ЭЛЕМЕНТАРНЫЕ ПУТИ 59

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

Лемма 2.4. В автомате с п состояниями длина элементарного пути не может быть больше п-1, а длина элементарного контура не может быть больш,е п.

Путь, не являющийся элементарным, называется избыточным. В следующем параграфе будут рассмотрены некоторые задачи, в которых представляют интерес только элементарные пути. В случае, когда это имеет место, все члены niiUii ... у которых не все индексы /, 1,

/д, J различны, могут быть исключены из матрицы

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

Лемма 2.5. [Ж] [Ж]* содержит все элементарные пути, содержащиеся в [Ж]*

Доказательство. Процесс умножения [Ж] на [Ж]*, как следует из (2.21), эквивалентен увеличению длины Л каждого пути, представленного в [Ж]*, до длины k-\-l посредством присоединения к концу пути одной из дуг, представленных в матрице [Ж]. Если путь из k дуг матрицы [Ж]* или присоединенная дуга избыточны, то результирующий путь длины k-\-l также должен быть избыточным. Следовательно, произведение [Ж] [Ж]*, где [Ж] образуется путем вычеркивания из [Ж] всех избыточных путей длины 1 и [Ж]** образуется путем вычеркивания из [Ж]** всех избыточных путей Длины k, должно содержать все элементарные пути, содержащиеся в [Ж] [Ж]*. Так как [Ж] [Ж]* = [Ж]*+\ то лемма доказана.

Лемма 2.5 означает, что в процессе построения [Ж]*"*" из [Ж] все избыточные пути можно исключать по мере их

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

упрощенный метод получения [Ж]* значительно менее трудоемкий, чем метод, по которому сперва получают [М]" и затем исключают из [Ж]* все избыточные пути.

Алгоритм 2.4. Дана [Ж], надо построить [Ж]" для /> 1. (1) Строим [Ж1, заменяя все диагональные элементы

в [Ж] нулями. Полагаем k=l. (2) Строим [Ж] [Ж]*. В произведении матриц заменяем каждый член, представляющий избыточный путь, нулем. Пусть результирующая матрица будет [Ж]*"". (3) (а) Если /г + 1 то увеличиваем Л на 1 и возвращаемся к (2). (б) Если k-\-l=l, то

[Жf=lЖ]".

Матрицы (2.26)-(2.29) иллюстрируют применение алгоритма 2.4 для построения [А1], [Alf по матрице [А1], представленной выражением (2.24)

[AlT и [Alf

(2.26)

/,(2

(2.27)

[AlT =

(2.28)

(2.29)

Можно заметить, что, в то время как число ненулевых членов в [УИ]* имеет тенденцию расти по экспоненте с ростом k, число членов в [Ж]* имеет тенденцию оставаться постоянным до определенного значения величины k и уменьшаться для больших значений k. Действительно, из леммы 2.4 можно заключить, что если М является автоматом с п состояниями, то [Ж]* для всех kn состоит полностью из нулевых членов.

2.11. Определение минимальных путей и полных контуров

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

Лемма 2.6. Минимальный путь, ведущий из состояния о,- в Oj, если он существует, должен быть элементарным путем.