В смежные состояния в Р, представляют собой -эквивалентные состояния, первые преемники которых по отношению к любому входному символу являются -эквивалентными. Поэтому такие смежные состояния являются (А1)-эквива-лентными и должны быть смежными в P + i- Пары смежных состояний в Р, которые при некотором входном символе переходят в разобщенные состояния в Р/, представляют собой -эквивалентные состояния, первые преемники которых по отношению к некоторому входному символу являются ft-различимыми. Поэтому такие смежные состояния являются {k -\- 1)-различимыми и должны быть разобщенными bP/j. Два разобщенных состояния в Р должны быть разобщенными также в P+i. Таким образом, Pi может быть определено по Р делением состояний каждого класса Р на подклассы таким образом, чтобы два состояния находились в одном и том же подклассе тогда и только тогда, когда их первые преемники по отношению к каждому входному символу являются смежными состояниями в Р. Полученные подклассы являются классами P+j. Поскольку одноэлементные классы не могут быть разделены на подклассы, то такие классы Р могут быть автоматически включены в P + i.

Рассмотрим, например, разбиение Р3 для автомата Л7, приведенное в (3.2). Первые преемники состояний 1, 3 и 8 являются смежными в при подаче а или р и в 2з, при подаче у. Первые преемники состояний 5 и 7 являются смежными в S33, если приложен входной символ а, в S32, если приложен символ р, и в Sjj, если приложен символ у. Следовательно, {1,3.8} и {5, 6} являются классами Р. Первые преемники состояний 2 и 4 по отношению к каждому входному символу являются смежными состояниями в Р3; поэтому {2, 4} являются классом Р. Одноэлементные классы {6} и {9} переходят в Р4 без изменений. Полученное разбиение Р будет таким, как показано в (3.3).

Таким образом, мы описали правила для последовательного построения Pj для k=\, 2, 3, ... Если для каждого входного символа каждая пара смежных состояний Р переходит в смежные состояния Р/,, то никакое дальнейшее разбиение Pj невозможно и, следовательно, Р = Р. Описанные правила поэтому дают способ определения эквивалентного разбиения заданного автомата.

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

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

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

Таблица Р заданного автомата, по существу, представляет собой то же, что и подтаблица s.i для этого автомата со следующими отличиями: (1) Если о;, о.....o/J

представляют собой класс Р, то строки о;, ot.....О/

группируются вместе, при этом каждая группа строк отделяется линией от соседних групп. Порядок групп в таблице и порядок строк в каждой группе произвольны. Строки, принадлежащие к одной и той же группе и, следовательно, представляющие класс fe-эквивалентности, будем называть смежными строками; строки, принадлежащие к различным группам, будем называть разобщенными строками. (2) Добавляется столбец 2, в котором указывается обозначение групп в таблице Р. Обозначение групп произвольно и может выбираться независимо в каждой новой таблице Р. (3) Каждое значение s снабжается индексом, указывающим группу, к которой данное значение относится. Так, если строка О; находится в группе, обозначенной «а», то каждое значение 0( в подтаблице si снабжается индексом «а».

Таблицы 3.3-3.6 являются таблицами Pj, з " для автомата Л7, изображенного на рис. 3.3.

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

Построение таблицы Pji по таблице Pj(&>-1). Две смежные строки в таблице Р, имеющие во всех столбцах

Таблица 3.3 Р, для автомата Л7

Таблица 3.4 Р% для автомата XI

Таблица 3.5 Рз для автомата Al

Таблица 3.6 Р4 для автомата А1