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

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

Если известны способы построения таблицы Рр а также таблицы Р;, по таблице Pikl), то можно строить таблицы Pf для последовательных значений k до тех пор, пока не будет получена таблица, в которой все смежные строки имеют одинаковые индексы во всех столбцах. В основном столбце в этих смежных строках обозначены эквивалентные состояния, а следовательно, группы последних представляют собой искомые классы эквивалентности. Согласно теореме 3.5, это условие должно иметь место для некоторого значения kn-1. Для автомата Л7 этому условию удовлетворяет таблица Р4 (таблица 3.6).

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

Р: {1, 3, 8}, {2, 4}, {5. 7], {6}. {9}. (3.9)

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

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

ЭТОЙ таблицы, в результате получается серия таблиц, k-я из которых называется к-м вариантом таблицы пзр. В первоначальной таблице(в первом варианте таблицы пар) основной столбец, называемый столбцом пар, содержит все неупорядоченные пары 1-эквивалентных состояний {а, Oj], где Кроме того, таблица имеет по столбцу на каждый символ входного алфавита. В клетке таблицы, находящейся на пересечении строки [Oi, Oj] и столбца lf, записываются первые

преемники О; и Oj по отношению к Порядок расположения пар в столбце пар и порядок записи состояний в клетках таблицы произвольны. Таблица пар может быть построена непосредственно по таблице переходов, в которой 1-эквивалентными являются состояния, представляющие одинаковые строки в подтаблице z. Таблица 3.7 представляет собой первый вариант таблицы пар автомата А7 (см. рис. 3.3).

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

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

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

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

) k - номер пары, d-номер класса эквивалентности. {Прим. перев.)

мыми, а следовательно и А-различимыми), то пары состояний, выделенные в процессе построения (к-{-1)-то варианта по к-му варианту, должны быть 1)-различимыми; пары

в клетках основного столбца, оставшиеся невыделенными, должны быть 1)-эквивалентными. Поскольку невыделенные пары в k-M варианте представляют собой все fe-эквива-лентные пары состояний автомата М, то невыделенные пары в (ft-f- 1)-м варианте должны представлять собой все (ft-j- 1)-эквивалентные пары автомата М. Тогда, по индукции, лемма справедлива для всех kl.

Если fe-й вариант является последним вариантом таблицы пар (т. е. вариантом, в котором все пары в клетках основного столбца выделены или в котором не может быть получено новых выделенных пар, то невыделенные пары в k-м варианте представляют собой все -эквивалентные пары, где k может быть сделано сколь угодно большим. Эти пары поэтому являются всеми парами эквивалентных состояний заданного автомата. Согласно теореме 3.5, это может иметь место для некоторого значения k<n - 1. Классы эквивалентности могут быть составлены из эквивалентных пар на основании того факта, что если а/, О/.....О/} является классом эквивалентности, то {а;, aj, {О/, aJ.....{r i Л являются

эквивалентными парами. В частности, составление классов эквивалентности может быть выполнено с помош.ью следующего алгоритма.

Алгоритм 3.1. Дано множество всех эквивалентных

пар состояний автомата М, {о/,, Oj,}, {о/,, aj,].....{о;, oyj;

требуется найти эквивалентное разбиение автомата М: (1) Пусть ft = 1 и d = 1). (2) Начнем рассмотрение с d-ro класса эквивалентности, приписав к нему пару {о/, Ojy (3) (а). Если fe < /, то увеличим fe на 1 и перейдем к (4). (б). Если k = l,Tod классов эквивалентности и одноэлементные классы, содержащие состояния, не включенные в какой-либо из d классов, образуют эквивалентное разбиение М. (4) (а) Если оба состояния в о/, Oyj входят в какой-либо ранее рассмотренный класс, то вернемся к (3). (б) Если только одно из состояний Jo/j, aj входит в какой-нибудь ранее рас-