2.81 МАТРИЦА ПЕРЕХОДОВ 53

Если р - МОЩНОСТЬ входного алфавита автомата М, то каждая строка в \М] должна содержать точно р пар вход-выход, причем каждая пара имеет входной символ, отличный от входного символа любой другой пары. Дуги, заходящие в состояние о, представляются недиагональными элементами ) столбца о; дуги, исходящие из состояния а, представляются недиагональными элементами строки а; петля состояния представляется диагональным элементом в строке или столбце Oj. Следовательно, если - переходящее состояние, то все недиагональные элементы в столбце (но не в строке Oj) равны нулю; если Oj-тупиковое состояние, то все недиагональные элементы в строке (но не в столбце Oj) равны нулю; если -изолированное состояние, то все недиагональные элементы в строке и столбце равны нулю.

Если S; = a;, О;.....а,-, то определенное в § 2.6

множество Gi(S,.) представляет собой объединение и обозначений столбцов, в которых элементы, принадлежащие строкам а,, о, .... о,-, не равны нулю. Определенное в § 2.7 множество H{Si) представляет собой объединение 5,., обозначений столбцов, в которых элементы, принадлежащие строкам 0;, .....о,., не равны нулю, и

обозначений строк, в которых элементы, принадлежащие

столбцам а,, о,......о,-, не равны нулю. Например, из

матрицы \А\] ясно видно, что для автомата А\ 0{\, 2) = = {1, 2, 3) и Я, (4, 5)= {1. 3, 4. 5). Таким образом, ясно, что матрица переходов является удобным инструментом для выполнения алгоритмов 2.1, 2.2 и 2.3.

Для того чтобы определить, составляет ли множество 5,.(а,-, .....О;) преходящий, тупиковый или изолированный подавтомат автомата М, надо строки и столбцы матрицы [М] переставить так, чтобы строки и столбцы о.....о,. заняли соседние положения, начиная с первой строки и первого столбца соответственно. Как показано в (2.13), эта перестановка делит матрицу [М] на четыре подматрицы [Жп], [Mij], [Mji], [Mjj], причем строками и

) Диагональный элемент матрицы - это элемент (/, у), где / = j. Недиагональный элемент матрицы - это элемент (/, Д ГД Ф j-

Таблицы, графы и матрицы переходов

:гл. 2

столбцами [AIji] являются строки и столбцы о, о.....о,-.

[М] =

О/, 1, • • •

22 J

(2.13)

Обозначая матрицу, все элементы которой равны нулю, через [0], можно сделать вывод, что 5 составляет преходящий подавтомат, если [Al2i] = [0], а [Ж12]=70, тупиковый подавтомат, если [Ж121 = [0], а [Ж211 О, и изолированный подавтомат, если [/VIi2] = [Ж21] = [0]. В (2.14) представлена матрица переходов автомата ЛЗ, изображенного на рис. 2.5, в которой строки и столбцы переставлены так, чтобы выделить тупиковый подавтомат {1, 4, 7), преходящий подавтомат (2, 5, 8) и изолированный подавтомат (3, 6, 9).

[Л3] =

(2.14)

Если S; составляет тупиковый или изолированный подавтомат, то [Ж12] = [0] и, следовательно, каждая строка в [Жц] содержит все р пар вход-выход, где р - мощность входного алфавита. Удалив [12], [21] и [Л122] из [М],

Рис. 2.9. Путь я/я,; •ik-ii-

ПцЛ11... ik-iJ Поскольку несуществующая дуга по определению соответствует нулевому сомножителю, то, если хотя бы одна дуга на пути, символически изображаемом вышеприведенным произведением, не существует, то все произведение становится равным нулю. Множество путей записывается как неупорядоченная сумма произведений; каждое произведение представляет элемент этого множества. Таким образом,

PV = Д Д .. 2 Vhhhh (2.15)

получим матрицу [Жц] размером г У, г, которую можно трактовать как матрицу, представляющую независимый автомат с г состояниями, имеющий тот же входной

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

2.9. Матрицы переходов высшего порядка

Последовательность k дуг, которая в графе переходов ведет из одного состояния в другое, называется путем; k называется длиной пути. Рг* обозначает множество всех путей длины k, которые ведут из состояния о,- в состояние Оу. Множество P*/j, которое состоит из одной дуги, ведущей из о,- в Оу, будем обозначать лу. Если Р*/] пусто (т. е. если ни одна дуга не ведет из о,- в Оу), то ему придается значение О (нуль).

Путь длины k, представляющий собой упорядоченную

последовательность дуг п, л,,.....ik-\i {V<- 2.9),

символически изображается упорядоченным произведением