Основная трудность - разрастание объема исходного языкового описания при попытке выяснить взаимоотношения его элементов. Идея обрабатывать языковое описание по частям естественна, и примеры ее воплощения возникли давно. Но эти разработки базируются на явлениях, причина которых не объясняется авторами. Механизм разделения на части остается таинственным; не ясно, в чем и насколько радикально можно его совершенствовать.

В данной работе, по существу, сделана попытка объяснить такие механизмы. Повидимому, попытку можно считать удачной, хотя и не совсем законченной. Успех во многом обусловлен графической интерпретацией традиционных синтаксических описаний бесконтекстных языков. Незаконченность состоит в том, что не предложен способ разделения сильно связных компонент D графов, а они мо гут быть очень велики.

3.1. Построение регулярного выражения по конечному автомату. Регулярные языки играют большую роль в математических теориях и в приложениях. Обширные библиографии по этому поводу имеются во множестве легко доступ ных источников. Упомянем здесь только работу [Мартыненко 98], которая посвящена методике и технологии синтаксически управляемой обработки данных и в которой используются понятия регулярного выражения и конечного автомата.

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

Предлагаемое здесь (см. также [Stanevichene -Vylitok 2000]) построение ре -курсивно, как и построение, принадлежащее Клини, но представляется нам лег че воспринимаемым. В самом деле, в нашем алгоритме автомат трактуется как достаточно естественная система подавтоматов, тогда как алгоритм Клини бази руется на произвольном упорядочении состояний (иначе, вершин) и на связанной с ним весьма формальной классификации путей. Существуют и другие доказа -тельства теоремы Клини; одно из последних содержится в [Melnikov Vakhitova 98]. Но они также не указывают естественного способа расчленения автомата и не позволяют привлечь испытанные приемы обработки графов.

Наше построение использует для выделения сильно связных компонент (это одна из основных частей построения) алгоритм из [Рейнгольд -Нивергельт -Део

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

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

Конечный автомат (над алфавитом Е) есть пятерка

A = (K, Е, 5, po, F),

K - конечное множество состояний, или вершин; Е - входной алфавит (также конечный); 5 С K х (Е U {Л}) х K - множество команд, или дуг; p0 - начальное состояние;

F С K - множество заключительных состояний.

Можно говорить о пути на графе A - пути конечного автомата A. Начальную и конечную вершины пути T обозначим через beg(T) и end(T) соответственно.

Пусть T - такой путь, что beg(T) = p0, а end(T) G F. Тогда T будем называть успешным путем или предложением. Введем обозначение для множества всех успешных путей конечного автомата A:

Sentences(A) = {T T - успешный путь конечного автомата A}.

Пусть Е - некоторый алфавит, не содержащий символов *, +, е, 0, (, ). Определим рекурсивно регулярное выражение над алфавитом Е (это специфическое слово в алфавите

Alph = Е U {*, +, е, 0, (, ) }) :

1)a G Е U {е, 0} является регулярным выражением;

2)если а и в - регулярные выражения, то

а)а + в - регулярное выражение; подвыражения а и в данного выражения будем называть его слагаемыми, само выражение - суммой;

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

в)(в)* - регулярное выражение, называемое итерацией выражения в.

3.1.2. Иерархия в конечном автомате. Напомним необходимые здесь понятия теории графов.

Ориентированный граф сильно связен, если для каждых его двух вершин и и v существует путь как из u в v, так и из v в и.

Пусть подграф G = (V, E) некоторого ориентированного графа сильно связен и любой отличный от G подграф (V,E), такой, что V С V, E С E, не является сильно связным. Тогда назовем G сильно связной компонентой данного графа.

Связный граф с одной вершиной и пустым множеством дуг будем называть тривиальным.

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

Пусть B - подграф конечного автомата над алфавитом Е, C = (V,E) - нетривиальная сильно связная компонента графа B, п Е E. Тогда обозначим конечный автомат (V, Е, E - {п}, end(n), {Ьвд(п)}) через Finite(B, п).

Пусть C - связный подграф конечного автомата. Определим рекурсивно ранг rank(C) этого подграфа:

1)rank(C)=0, если C - тривиальная сильно связная компонента;

2)rank(C) = 1 + min{rank(Finite(C, п)) п - дуга графа C}, если граф C совпадает со своей нетривиальной сильно связной компонентой;

3)rank(C) = max{rank(B) B - сильно связная компонента графа C}.

3.1.3. Преобразование конечного автомата в регулярное выражение

Обозначим через Lines(A) множество предложений автомата A, не содержащих циклов:

Lines(A) = {T Е Sentences(A) \/(T\,T2,T3) T = TiT2T3 =>- (T2 не является циклом)}.

Определим рекурсивно регулярное выражение E(A) над алфавитом дуг автомата A; при этом каждый пустой путь будем считать синонимом обозначения Л:

E (A) =Cycles(beg(T))Addend(T),

T ebines(A)

{е, путь T пуст, ПlCycles(end(пl))...ПkCyclesndk)), k > 1, T = п\...п], пi Е 5, 1 < i < k,

где вспомогательное выражениесумма Cycles(p), p Е K, определяется в следующем абзаце.

Если p является вершиной нетривиальной сильно связной компоненты, то

Cycles(p) = (Bound))*,

п- дуга сильно связной компоненты,

Ъвд(ж)=р

Cycles(p) = p;

здесь для дуги п сильно связной компоненты B автомата A

Bound) = п(Е (Finite))).

Теорема 8. L(E (A)) = Sentences (A).

Доказательство. Индукцией по r = rank(A). При r = 0 предложения автомата не имеют циклов, т.е. справедливо равенство Lines (A) = Sentences(A). Следовательно, формула для E(A) упрощается в данном случае до

E (A) = £ T

T 6 Sentences (A)

и теорема верна.

Пусть r > 0. Предположим, что теорема выполняется для каждого автомата, ранг которого не превышает r - 1, и рассмотрим автомат A ранга r.