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

В разделе 3.1 определяется КСвыражение. Определяется ряд понятий (ядро, развитие и т.д.), распространяющих наш подход к исследованию бесконтекстных языков на введенный новый формализм.

Раздел 3.2 рассматривает алгоритмы, преобразующие Dграф в КСвыражение и КС выражение в D граф. В разделе 3.3 определяются согласующее и псев досогласующее КСвыражения. Доказывается утверждение об эквивалентности псевдосогласующих выражений регулярным.

3.1. КСвыражения. Весьма соблазнительна попытка построить обобщение ре -гулярных выражений, которое задает в точности бесконтекстные языки и исполь зует, кроме алфавита языка, некоторый не зависящий от языка конечный набор символов. Известная лемма Огдена, вид формантов, используемых для развития маршрутов Dграфа, и вид элементарных итераций [Станевичене 96б] наталкивают на добавление к регулярным операциям операции, языкотворческий эффект которой таков же, как у системы бесконтекстных правил (вообще говоря, беско нечной)

S - z\xSy, z G Z С X*, (x, y) G X x Y С X* x X*.

Трудность, однако, в том, что языки Z, X и Y могут определяться с помощью языка L, порождаемого данными правилами, и места вставления парных цепочек x G X и y G Y не подчиняются какомуто общему для всех бесконтекстных языков закону. Места вставления различных "интерферирующих"конструкций могут располагаться в пределах некоторой цепочки так, что только индивидуальные их обозначения помогут разобраться, в каком месте что вставляется. В связи с этим вводится понятие именования. У операции именования два операнда: имя (это элемент некоторого конечного множества) и выражение, которому данное имя сопоставляется. Она старше используемых в КС выражении регулярных опера ций объединения и сцепления.

Употребление именованного подвыражения внутри выражения с тем же име нем обеспечивает размножение вхождений в цепочку языка некоторых подцепо чек. Число используемых в выражении имен, вообще говоря, зависит от языка. Привычные средства описания синтаксической иерархии подцепочек в цепочках бесконтекстного языка побуждают выразить операцию именования посредством окаймления операндавыражения скобками (t и )t, где i - операндимя. С выбором нотации связана полезность при изучении КС выражений рассмотренных в параграфе 1 комбинаторных свойств скобочных систем.

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

Для любых алфавитов Еь Е2 и цепочки x G (Si U Е2)* обозначим результат вычеркивания из x всех символов алфавита Е1 - Е2 через

projection(x, Е2).

Пусть Names - непустое конечное множество, B = {(t, )L\i G Names}. Пусть множества Е, B и {+,е, 0, (,)} попарно не пересекаются, Alph = Е UBU 0, (,)}. Определим рекурсивно КСвыражение над алфавитом Е (это специфическое слово в алфавите Alph):

1)a G Е U {е, 0} - КСвыражение;

2)если а и в - КСвыражения, то:

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

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

3)если i G Names и в - КСвыражение, то (в)t есть (именованное) КС-выражение, или 1-гнездо.

Пусть множества Names, B и Alph применяются в некотором КСвыражении ( так, как это указано последним определением. Тогда обозначения Alph(Z), B(Z) и Names(() будут использоваться для множеств

{c G Alph\3(u, v G Alph*) Z = ucv}, B П Alph(Z)

{1 G Names\(LG B(Z)}

соответственно.

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

Назовем фракцией КСвыражения над алфавитом Е элемент следующего рекурсивно определяемого множества КС выражений:

1)Fractions (a) = {a} для a G Е U {е, 0};

2)если а и в суть КСвыражения, то

Fractions)) = Fractions), Fractions(a + в) = Fractions (a) U Fractions), Fractionsa))) = Fractions(a) Fractions (в),

Fractionsd )t) = {(<.} Fr actions (в) {)<.}.

Из определения фракции следует, что она выглядит как КСвыражение, которое не содержит сумм и безымянных скобок. На этом основании иногда уместно называть фракцией любую цепочку, которая имеет вид КС выражения без сумм и безымянных скобок, не уточняя, какого КС выражения эта фракция; в частности, мы будем называть фракцией каждый элемент определяемого далее клана КС выражения.

Для фракции Z над алфавитом X назовем ее пометкой следующее рекурсивно определяемое множество С X*:

"(С)

{а}, С = а е X;

{Л}, С = с; 0, С = 0;

ш(а)ш(Р), С = ав, а и в - фракции; С =в - фракция.

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

Пусть фракция совпадает с 0 или не содержит подвыражения 0. Тогда назовем фракцию приведенной.

Результат приведения некоторой фракции £ обозначим через trim(£). Приведение можно осуществить, повторяя, пока присутствуют гнездо вида (t0)t или произведение какоголибо из видов а0, 0а, замену гнезда на с, а произведения на

Обозначим через ТНт(С) множество всех отличных от 0 приведенных фракций КС выражения С:

ТНт(С) = {trim(£)£ - фракция выражения С} - {0}.

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

Клан, порождаемый КСвыражением С, определим рекурсивно:

С/ап(С) = Тпт(С) иШХвз

ai(ta2)ta3,ei(te2Хвз е С/ап(С)}. Из этого определения видно, что клан КСвыражения может отличаться от множества его приведенных фракций, если в КС выражении несколько подвыра жений одним и тем же именем. Действительно, для образования клана любое из именованных подвыражений может быть заменено любым одноименным. Замена, как увидим, "реализует"разрастание цепочек языка (см. ниже о понятиях цикла, развития и новом взгляде на образование клана).

Язык, задаваемый КСвыражением С, есть подмножество

GClan(C)

множества X*. Язык пуст, если пуст клан.

Следующие определения легче понять, если вспомнить, что для любого КС выражения С и для любого подмножества B алфавита именованных скобок В(С)