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

Определение эквивалентного разбиения автомата может быть произведено также с помощью так называемой таблицы пар. Разбиение выполняется последовательным изменением этой таблицы. В результате получается серия таблиц, k-я из которых называется k-м вариантом таблицы пар. В первоначальной таблице (в первом варианте таблицы пар) основной столбец, называемый столбцом пар, содержит все неупорядоченные пары 1-эквивалентных состояний {σ _i, σ _j }, где i≠ j. Кроме того, таблица имеет по столбцу на каждый символ ξ _h входного алфавита. В клетке таблицы, находящейся на пересечении строки { σ _i, σ _j } и столбца ξ _h, записываются первые преемники σ _i и σ _j по отношению к ξ _h. Порядок расположения пар в столбце пар и порядок записи состояний в клетках таблицы произвольны. Таблица пар может быть построена непосредственно по таблице переходов, в которой 1-эквивалентными являются состояния, представляющие одинаковые строки в подтаблице z _v. Таблица 3.7 представляет собой первый вариант таблицы пар автомата А7 (см. рис. 3.3).

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

Построение (k+l)-гo варианта таблицы пар по k-му варианту (А^-1). Рассмотрим каждую невыделенную строку в k-м варианте; сделаем строку выделенной, если в ней имеется отличающаяся пара, которая либо отсутствует в основном столбце пар, либо выделена жирным шрифтом в этом столбце. Таблица, полученная после рассмотрения последней невыделенной строки, будет (k + 1)-м вариантом таблицы пар.

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

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

Если k-й вариант является последним вариантом таблицы пар (т. е. вариантом, в котором все пары в клетках основного столбца выделены или в котором не может быть получено новых выделенных пар, то невыделенные пары в k-u варианте представляют собой все k-эквивалентные пары, где k может быть сделано сколь угодно большим. Эти пары поэтому являются всеми парами эквивалентных состояний заданного автомата. Согласно теореме 3.5, это может иметь место для некоторого значения k ≤ n - 1. Классы эквивалентности могут быть составлены из эквивалентных пар на основании того факта, что если {σi ₁, σi ₂,..., σi _r }является классом эквивалентности, то {σi ₁, σi ₂ }, {σi ₂, σi ₃ },..., {σi _r-1, σi _r } являются эквивалентными парами. В частности, составление классов эквивалентности может быть выполнено с помощью следующего алгоритма.

Алгоритм 3.1. Дано множество всех эквивалентных пар состояний автомата М, {σi ₁, σj ₁ }, {σi ₂, σj ₂ },..., {σi _l, σi _l }требуется найти эквивалентное разбиение автомата М: (1) Пусть k = 1 и d = 1 [19]. (2) Начнем рассмотрение с d-ro класса эквивалентности, приписав к нему пару {σi _k, σi _k }.(3) (а). Если k < l, то увеличим k на 1 и перейдем к (4). (б). Если k = l, то d классов эквивалентности и одноэлементные классы, содержащие состояния, не включенные в какой-либо из d классов, образуют эквивалентное разбиение М. (4) (а) Если оба состояния в {σi _k, σi _k } входят в какой-либо ранее рассмотренный класс, то вернемся к (3). (б) Если только одно из состояний {σi _k, σi _k } входит в какой-нибудь ранее рассмотренный класс, то добавим второе состояние пары в этот класс и вернемся к (3). (в) Если ни одно из состояний {σi _k, σi _k } не входит ни в какой из ранее рассмотренных классов, то увеличим d на 1 и вернемся к (2).

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

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

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