2.8. Матрица переходов

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

Для автомата М, имеющего n состояний, матрица переходов состоит из n строк и n столбцов и обозначается Пусть -множество состояний автомата М и пусть обозначает дугу графа переходов автомата М, направленную от Элемент (т. е. содержимое клетки, расположенной на пересечении строки и столбца матрицы обозначается и определяется так:

Для ясности обычно обозначение состояния приписывают строке и столбцу и называют их «строка » и «столбец » соответственно. Выражение (2.12) изображает матрицу переходов автомата А 1, заданного в виде графа на рис. 2.2.

Если p — мощность входного алфавита автомата М, то каждая строка в [М] должна содержать точно p пар вход - выход, причем каждая пара имеет входной символ, отличный от входного символа любой другой пары. Дуги, заходящие в состояние представляются недиагональными элементами столбца дуги, исходящие из состояния представляются недиагональными элементами строки петля состояния представляется диагональным элементом в строке или столбце Следовательно, если переходящее состояние, то все недиагональные элементы в столбце не в строке равны нулю; если — тупиковое состояние, то все недиагональные элементы в строке не в столбце равны изолированное состояние, то все недиагональные элементы в строке и столбце равны нулю.

Если то определенное в § 2.6 множество представляет собой объединение и обозначений столбцов, в которых элементы, принадлежащие строкам не равны нулю. Определенное в § 2.7 множество представляет собой объединение обозначений столбцов, в которых элементы, принадлежащие строкам не равны нулю, и обозначений строк, в которых элементы, принадлежащие столбцам не равны нулю. Например, из матрицы ясно видно, что для автомата . Таким образом, ясно, что матрица переходов является удобным инструментом для выполнения алгоритмов 2.1, 2.2 и 2.3.

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

столбцами являются строки и столбцы о,

Обозначая матрицу, все элементы которой равны нулю, через [0], можно сделать вывод, что составляет преходящий подавтомат, если тупиковый подавтомат, если , и изолированный подавтомат, если В (2.14) представлена матрица переходов автомата А3, изображенного на рис. 2.5, в которой строки и столбцы переставлены так, чтобы выделить тупиковый подавтомат , преходящий подавтомат и изолированный подавтомат

Если составляет тупиковый или изолированный подавтомат, то и, следовательно, каждая строка в содержит все p пар вход - выход, где p — мощность входного алфавита. Удалив

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