смотренный класс, то добавим второе состояние пары в этот класс и вернемся к (3). (в) Если ни одно из состояний о/, oyl не входит ни в какой из ранее рассмотренных классов, то увеличим d на 1 и вернемся к (2).

Таблицы 3.7 - 3.10 иллюстрируют построение первых четырех вариантов таблиц пар автомата А7. Все построение может быть, конечно, выполнено на одной первоначальной таблице; ряд таблиц приведен только для того, чтобы показать последовательно шаги построения. Таблица 3.10 является таблицей пар в ее окончательной форме с эквивалентными парами {1,3}, {1,8}, {2,4}, {3,8} и {5,7}, не выделенными жирным шрифтом в основном столбце. Применяя алгоритм 3.1,

Таблица 3.7 Таблица пар для автомата А7 (первый вариант)

Таблица 3.8 Таблица пар для автомата А7 (второй вариант)

Таблица 3.9 Таблица пар для автомата АЛ (третий вариант)

Таблица 3.10

Таблица пар для автомата А1 (четвертый вариант)

получаем эквивалентное разбиение {1, 3, 8}, {2, 4}, {5, 7}, {6} и {9}, совпадающее с приведенным в (3.9).

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

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

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

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

Матрица [Ж]** для автомата М является матрицей [М\, в которой симметрическая перестановка и симметрическое разбиение обладают следующими свойствами: строки (и столбцы), соответствующие смежным состояниям Pj, сгруппированы вместе, а каждая группа отделена от соседних групп пунктирными линиями; порядок групп в матрице и порядок строк (столбцов) в каждой группе произвольны; если Р содержит fj классов, то симметрическое разбиение образует Tj рядов подматриц с подматрицами в каждом ряду.

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