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

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

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

Доказательство. Пусть минимальный путь выражается так: πi l ₁πi₁ l ₂... π l _k-1j и имеет длину k. Если этот путь избыточный, то имеются два индекса среди i, l₁,l₂,..., l_k-1,j, которые одинаковы. Предположим, что l_g = l_h, где h>g. Тогда минимальный путь может быть представлен произведением

Если этот путь существует, то в этом произведении нет множителей, равных нулю. Следовательно, нет равных нулю множителей и в произведении πi l ₁πi₁ l ₂... π l_g-1l _g π l_gl_h+1... π l _k-1 j, а это означает, что такой путь тоже существует. Так как последний путь короче, чем предыдущий, и, так же как предыдущий, ведет из σ _i в σ_j, предыдущий путь не может быть минимальным. Отсюда следует, что предположение, сделанное в начале доказательства, неверно, т. е. минимальный путь не может быть избыточным.

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

Теорема 2.4. Если существует путь, который ведет из состояния σ _i в состояние σ_j в автомате M c n состояниями, то кратчайший такой путь представляется некоторым элементом (i, j) одной из матриц , где 1 ≤ k ≤ n — 1.

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

Алгоритм 2.5. Для того чтобы определить минимальный путь, ведущий из состояния σ _i в σ_j, в автомате М с n состояниями надо произвести следующие операции: (1) Полагаем k=1. (2) Строим . (3) (а) Если элемент (i, j) равен нулю и k < n — 1, то увеличиваем k на единицу и возвращаемся к (2). (б) Если элемент (i, j) равен нулю и k = n—1, то путь из σ _i в σ_j не существует, (в) Если элемент (i, j) не равен нулю, то он представляет искомый путь (или пути).

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

пока первый раз элемент, расположенный на пересечении строки 1 и столбца 5, примет значение, отличное от нуля, или пока k станет равным 5 (в последнем случае путь не существует). Матрицы (2.26) — (2.29) показывают, что первый отличный от нуля элемент, расположенный на пересечении строки 1 и столбца 5, появляется в матрице , где этот элемент равен π₁₃π₃₄π₄₅. Обращение к графу переходов рис. 2.2 или к матрице переходов (2.12) показывает, что минимальным путем можно пройти, если подать входную последовательность und.

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

Лемма 2.7. Главная диагональ матрицы содержит все полные контуры автомата М. Доказательство. Так как полный контур является элементарным контуром, то любые n—1 последовательных дуг составляют в полном контуре длины n элементарный путь. Множество всех путей, построенных добавлением к элементарным путям длины n—1 элементарных путей длины 1, содержит поэтому все полные контуры длины n. Значит, содержит это множество, и, следовательно, полные контуры являются путями, ведущими из любого состояния в то же самое состояние. Лемма доказана.

Очевидно, любое состояние автомата М может рассматриваться как начальное состояние в полном контуре. Следовательно, если один диагональный элемент в равен нулю, что имеет место при отсутствии полных контуров в автомате М, то все диагональные элементы в этой матрице должны быть равны нулю. Любой ненулевой диагональный элемент (_{i, j}) в представляет собой множество всех возможных полных контуров в автомате М; диагональный элемент (_{i, j}), j ≠ i, представляет собой циклические перестановки сомножителей членов, содержащихся в элементе (i, j).

Например, в результате построения получилась матрица, в которой все элементы равны нулю; это значит, что А1 не содержит полных контуров. Рис. 2.6 и матрица (2.30). представляют автомат A4, в котором существует полный контур. Матрицы (2.31), (2.32) и (2.33) иллюстрируют процедуру определения этого контура. Так как число состояний в A4 равно 3, то матрица , представленная выражением (2.33), должна содержать все полные контуры на своей главной диагонали. Искомым полным контуром является контур π₁₂π₂₃π₃₁ или любой другой, полученный из него циклической перестановкой. Обращение к рис. 2.6 или к матрице (2.30) показывает, что если начальное состояние A4 есть 1, то полный контур можно пройти, подавая на вход βαα или βαβ.