3.6. Разбиение при помощи таблиц

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

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

Таблица заданного автомата, по существу, представляет собой то же, что и подтаблица для этого автомата со следующими отличиями: (1) Если представляют собой класс , то строки группируются вместе, при этом каждая группа строк отделяется линией от соседних групп. Порядок групп в таблице и порядок строк в каждой группе произвольны. Строки, принадлежащие к одной и той же группе и, следовательно, представляющие класс -эквивалентности, будем называть смежными строками, строки, принадлежащие к различным группам, будем называть разобщенными строками. (2) Добавляется столбец Е, в котором указывается обозначение групп в таблице Обозначение групп произвольно и может выбираться независимо в каждой новой таблице Каждое значение снабжается индексом, указывающим группу, к которой данное значение относится. Так, если строка находится в группе, обозначенной , то каждое значение в подтаблице снабжается индексом

Таблицы являются таблицами для автомата АТ, изображенного на рис. 3.3.

Построение таблицы Изменим порядок строк в таблице переходов таким образом, чтобы одинаковые строки в подтаблице стали соседними. Каждая группа таких строк соответствует классу -эквивалентности, и, следовательно, является группой смежных строк в таблице . Теперь можно построить таблицу путем вычеркивания подтаблицы разделения групп строк линиями, добавления столбца 2 и индексами значений как было описано выше. В качестве иллюстрации сошлемся на таблицы 3.2 и 3.3.

Построение таблицы по таблице . Две смежные строки в таблице имеющие во всех столбцах

Таблица 3.3. для автомата А 7

Таблица 3.4. для автомата А 7

Таблица 3.5. для автомата А 7

Таблица 3.6. для автомата А 7

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

В качестве примера рассмотрим таблицу автомата представленную таблицей 3.5. В группе одинаковые индексы во всех столбцах имеют строки 1, 3 и 8 и строки 5 и 7. (Индексы в строках 5 и 7 отличаются от индексов в строках 1,3 и 8.) Следовательно, строки 1, 3 и 8 и строки 5 и 7 образуют две группы строк в таблице . В группе «b» все строки имеют одинаковые индексы во всех столбцах, поэтому группа без изменений остается в таблице Группы , содержащие по одной строке, могут быть перенесены без изменения в таблицу

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

Эквивалентное разбиение для поэтому будет