3.8. Матричный метод разбиения

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

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

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

Построение матрицы Сгруппируем строки матрицы так, чтобы две строки принадлежали к одной и той же группе тогда и только тогда, когда они образуют одинаковые множества пар вход - выход. Каждая такая группа представляет собой класс -эквивалентности. Производя симметрическую перестановку и симметрическое разбиение в соответствии с правилами, описанными выше, получим . Примером матрицы переходов является матрица (3.10) автомата (рис. 3.3). Строки 1, 3, 5, 7 и 8 в представляют пары вход - выход Строки 2, 4, 6 и 9 представляют пары вход - выход и . Тогда матрица строится группировкой строк (и столбцов)

1, 3, 5, 7 и 8 и строк (и столбцов) 2, 4, 6 и 9, при этом группы разделяются пунктирной линией. Матрицей полученной в результате этих операций, является матрица (3.11).

Построение матрицы по . Пусть — две строки в одной и той же группе строк . Если в каждой из подматриц, пересеченных строками строки имеют одинаковые множества пар вход - выход, то представляют собой k - эквивалентные состояния, первые преемники которых по отношению к любому входному символу являются -эквивалентными, поэтому состояния являются -эквивалентными. Если эти условия не имеют места, то являются -различимыми. Таким образом, матрица может быть построена по если разделить каждую группу строк в на подгруппы так, чтобы две строки принадлежали одной и той же подгруппе тогда и только тогда, когда они имеют одинаковые пары вход - выход в каждой из пересекаемых ими подматриц . Каждая такая группа представляет собой -эквивалентный класс. Произведя симметрическую перестановку и симметрическое разбиение матрицы ), получим в результате Например, строки 1, 3, 5, 7 и 8 в имеют одинаковые множества пар вход - выход в каждой подматрице, которую они пересекают. С другой стороны, строки 2, 4 и 6 образуют в пересекаемых подматрицах множества пар вход - выход, которые отличаются от множества пар вход - выход, образованного строкой 9. Следовательно, строки 2, 4 и 6 и строка 9 дают две различные группы в как показано в (3.12).

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

(см. скан)

Матрицы (3.10)-(3.14) иллюстрируют описываемый метод эквивалентного разбиения автомата А 7. Матрица дальнейшее разбиение которой невозможно, очевидно, содержит эквивалентное разбиение совпадающее с разбиением (3.9).

(см. скан)