л,-, л

Если этот путь существует, то в этом произведении нет множителей, равных нулю. Следовательно, нет равных нулю множителей и в произведении лл,;.. .Л; iigigih+\ h-i а это означает, что такой путь тоже существует. Так как последний путь короче, чем предыдущий, и, так же как предыдущий, ведет из в Оу, предыдущий путь не может быть минимальным. Отсюда следует, что предположение, сделанное в начале доказательства, неверно, т. е. минимальный путь не может быть избыточным.

На основании лемм 2.4 и 2.6 можно теперь сформулировать следующую теорему.

Теорема 2.4. Если существует путь, который ведет из состояния в состояние Oj в автомате М с п состояниями, то кратчайший такой путь представляется некоторым элементом (i, j) одной из матриц [уИ1*>, где 1 < /г < w - 1.

Теорема 2.4 указывает следующую процедуру для определения минимальных путей.

Алгоритм 2.5. Для того чтобы определить минимальный путь, ведущий из состояния в Оу, в автомате М с п состояниями надо произвести следующие операции:

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

Например, для того чтобы найти минимальный путь, ведущий из состояния 1 в состояние 5 в автомате А\, строится матрица [ЛГ]* для k=\, 2, ... до тех пор,

Доказательство. Пусть минимальный путь выражается так: Лцл,,... л, у и имеет длину Л. Если этот путь избыточный, то имеются два индекса среди /, Zj, Zj, . . ., Zj i, J, которые одинаковы. Предположим, что lg=lh, где hyg. Тогда минимальный путь может быть представлен произведением

пока первый раз элемент, расположенный на пересечении строки 1 и столбца 5, примет значение, отличное от нуля, или пока k станет равным 5 (в последнем случае путь не существует). Матрицы (2.26) - (2.29) показывают, что первый отличный от нуля элемент, расположенный на пересечении строки 1 и столбца 5, появляется в матрице [ЛГ]**, где этот элемент равен Л13Л34Л45. Обращение к графу переходов рис. 2.2 или к матрице переходов (2.12) показывает, что минимальным путем можно пройти, если подать входную последовательность and.

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

Лемма 2.7. Главная диагональ матрицы \M\\Mf"~ содержит все полные контуры автомата М.

Доказательство. Так как полный контур является элементарным контуром, то любые п-1 последовательных дуг составляют в полном контуре длины п элементарный путь. Множество всех путей, построенных добавлением к элементарным путям длины п-1 элементарных путей длины 1, содержит поэтому все полные контуры длины п. Значит, [Ml [УИ]*""* содержит это множество, и, следовательно, полные контуры являются путями, ведущими из любого состояния в то же самое состояние. Лемма доказана.

Очевидно, любое состояние автомата М может рассматриваться как начальное состояние в полном контуре. Следовательно, если один диагональный элемент в [Ж] [Ж]*""* равен нулю, что имеет место при отсутствии полных контуров в автомате Ж, то все диагональные элементы в этой матрице должны быть равны нулю. Любой ненулевой диагональный элемент (/, /) в [MWMi" представляет собой множество всех возможных полных контуров в автомате Ж; диагональный элемент (у, у), у ф I, представляет собой

циклические перестановки сомножителей членов, содержащихся в элементе (/, 1).

Например, в результате построения [ЛГ] [ЛГ]* получилась матрица, в которой все элементы равны нулю; это значит, что Л1 не содержит полных контуров. Рис. 2.6 и матрица (2.30). представляют автомат Л4, в котором существует полный контур. Матрицы (2.31), (2.32) и (2.33) иллюстрируют процедуру определения этого контура. Так как

число состояний в Л4 равно 3, то матрица [Л41 [Л41**, представленная выражением (2.33), должна содержать все полные контуры на своей главной диагонали. Искомым полным контуром является контур л12л23л31 или любой другой, полученный из него циклической перестановкой. Обращение к рис. 2.6 или к матрице (2.30) показывает, что если начальное состояние Л4 есть 1, то полный контур можно пройти, подавая на вход раа или рар.

1 2 3

[Л41 = 2

3 L (а/О) V (Р/0) 1 2

Л41 = 2 3

L л.

[Л41 = 2

[Л41[Л4р=2 3

Л23Л31 . О

л12л23лз, о о

л31л12 2

л13л31л12 л23л31л12 О

(Р/1) (а/О)

(Р/0) (а/1) О О J

(2.30)

л23 О J

(2.31)

л12л23 О О

Лз[Л[2Л23 -

(2.32)

(2.33)