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

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

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

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

Построение варианта таблицы пар по варианту . Рассмотрим каждую невыделенную строку в варианте; сделаем строку выделенной, если в ней имеется отличающаяся пара, которая либо отсутствует в основном столбце пар, либо выделена жирным шрифтом в этом столбце. Таблица, полученная после рассмотрения последней невыделенной строки, будет вариантом таблицы пар.

Лемма 3.11. Невыделенные пары в клетках основного столбца в варианте таблицы пар автомата М образуют все -эквивалентные пары состояний автомата М.

Доказательство. Для лемма справедлива по построению. Предположим, что она справедлива для k. Тогда невыделенная пара в клетке основного столбца представляет собой пару k - эквивалентных состояний. Эти состояния являются -различимыми только тогда, когда их первые преемники по отношению, по крайней мере, к одному входному символу являются -различимыми. Так как такими преемниками являются либо выделенные пары в клетках основного столбца, либо отличающиеся пары, отсутствующие в основном столбце (эти последние пары являются 1-различимыми,

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

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

Алгоритм 3.1. Дано множество всех эквивалентных пар состояний автомата требуется найти эквивалентное разбиение автомата М: (1) Пусть Начнем рассмотрение с класса эквивалентности, приписав к нему пару (а). Если то увеличим k на 1 и перейдем к (4). (б). Если классов эквивалентности и одноэлементные классы, содержащие состояния, не включенные в какой-либо из d классов, образуют эквивалентное разбиение М. (4) (а) Если оба состояния в входят в какой-либо ранее рассмотренный класс, то вернемся к (3). (б) Если только одно из состояний входит в какой-нибудь ранее

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

Таблицы 3.7 — 3.10 иллюстрируют построение первых четырех вариантов таблиц пар автомата Все построение может быть, конечно, выполнено на одной первоначальной таблице; ряд таблиц приведен только для того, чтобы показать последовательно шаги построения. Таблица 3.10 является таблицей пар в ее окончательной форме с эквивалентными парами не выделенными жирным шрифтом в основном столбце. Применяя алгоритм 3.1,

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

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

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

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

получаем эквивалентное разбиение совпадающее с приведенным в (3.9).

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