Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[11]

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

Пусть T Е Lp П R. Тогда по лемме 9 T является нейтральным маршрутом. Так как из соотношения T Е R следуют соотношения first(T) Е A и last(T) Е B, нейтральный маршрут T успешен □

Теорема 6 (о морфическом представлении бесконтекстного языка). Пусть L С Е* - бесконтекстный язык. Тогда существуют такие Dязык L, локальный язык R и хороший (отображающий символ в символ или пустую цепочку [Eilenberg 74]) морфизм h, что

L = h(Ln R).

Доказательство. Так как L - бесконтекстный язык, он определяется некото рым Dграфом D. Используя множество дуг Dграфа D в качестве алфавита, определим локальный язык R, как в начале параграфа. Определим морфизм

h : E* - Е*

формулой

h(n) = со(тт), п Е E.

По теореме 5 множество успешных маршрутов совпадает с Lp П R. Так как определяемый D графом язык есть множество пометок всех его успешных маршрутов, верна формула L = h(LP П R) □

Следствие 1 (теорема ХомскогоШютценберже). Пусть L С Е* - бесконтекстный язык. Тогда существуют такие язык Дика L, локальный язык R и хороший морфизм h, что L = h(L П R).

Доказательство. Пусть LP - это язык Дика над некоторым Dмножеством р С Е( х Е), удовлетворяющим равенствам

Е( = Е) = р =

Пусть А = Е( U Е) и

ф : P - p

есть некоторая биекция. Можно сказать, что функция ф снабжает уникальным обозначением каждое вхождение в элементы Dмножества P скобок из E = Left(P) U Right(P).

Из определения функции ф следует сюръективность функции

С : А - E, заданной соотношениями (из равенств

Е( = Е) =

следует, что каждый символ алфавита А входит в некоторую пару из D множества р):

У (a, b) Е р С (a) = a, С (b) = b, ф(а, Ь) = (a, b). Здесь возможно равенство С(ci) = С(с2) при c\ = c2. Отметим, что функция С индуцирует побуквенный (отображающий символ одного алфавита в символ другого [Salomaa 81]) морфизм

С : А* - E*.


Из определения функции ф следует биективность функции

Ф : Lp - Lp

определяемой соотношениями

Ф(Л) = {Л},

Ф(п1Тп2) = аФ(Т)Ь, Т eLv, (тг1,7Г2) eV, (а,Ь) = ф(т ,п2),

Ф(тгт2) = Ф(Т1)Ф(Т2), Ti,T2 e Lp.

Для произвольной подцепочки Т цепочки из Lp обозначим через Ф(Т) множество {ж2(ЭТ1,Т2,Тз) (Т2 = Т, Т1Т2Т3 e Lp, ФСТ1Т2Т3) = Ж1Ж2Ж3, Ti = \xi\ для i = 1, 2, 3)}.

A = J Ф(п), B = U Ф(п), С = А2 - U Ф(П1П2).

R = (ЛА* П А*В) - А*СА* является локальным языком, а

{Ф(Т)Т является успешным маршрутом Dграфа D} = LP П R.

Теперь видна справедливость равенства

L(D) = h(Z(Lp П R)),

где h - морфизм, определенный в доказательстве теоремы 6. Так как композиция морфизмов есть морфизм и ( - морфизм побуквенный,

h = h( : А* - X*

является хорошим морфизмом. Построенные язык Дика LP, локальное множество R и хороший морфизм h позволяют вывести из теоремы 6 справедливость рассматриваемого утверждения □

§3. Одно обобщение регулярных выражений

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

1)Dграфы и КСвыражения характеризуют один и тот же класс языков;

2)класс так называемых псевдосогласующих КСвыражений эквивалентен классу регулярных выражений.

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

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


данному моменту результаты наших исследований по выявлению и адекватному выражению общей сути различных характеризаций бесконтекстных языков. В пользу таких поисков можно заметить следующее. С помощью понятия синтаксической конгруэнции [Lallement 79] регулярный язык можно представить системой компонентов, не зависящей от тех или иных способов его задания, приписывающих его цепочкам некоторую структуру. При этом существует определенная взаимосвязь между компонентами упомянутой системы и любым из возможных синтаксисов регулярного языка (подразумеваются синтаксические описания, изу чаемые в рамках теории регулярных языков). Именно наличие такой связи обеспечивает возможность отвечать на все вопросы о конечных автоматах.

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

При разработке обобщения регулярных выражений мы руководствовались сле дующими соображениями. Звездочка Клини качественно отличается от других регулярных операций. Ее смысл позволяет интерпретировать регулярное выраже ние а, задающее бесконечный язык, как описание формальной системы, теоремы которой фиксируют "синтаксический разбор относительно а"отдельных цепочек языка. Для обоснования этого тезиса обсудим регулярные выражения над неко -торым алфавитом Е.

Язык, заданный регулярным выражением а, обозначим через L(a).

Заметим, что в записи регулярного выражения а над алфавитом Е "рассре -доточены"цепочки, составляющие некоторое конечное подмножество L(a) языка L(a); L(a) можно определить рекурсивно:

L(0) = 0,

L(a) = {а} для a G Е U {б}, L(a) = L(e) U L(y) для а = в + 7, L(a) = L(e)L(7) для а = (e)(7), L) = {Л} U L(e) для а = (в)*.

Теперь возьмем в качестве аксиомы само выражение а, а в качестве правила вывода удвоение вхождения подвыражения вида (7)*, т.е. посылке вида

x(7 )* У,

где 7 - регулярное выражение и xy - регулярное выражение или пустая цепочка, отвечает заключение

x(7 )*(7 )*y-

Ясно, что

l) = у L(e).

в выводится из а

Мы задались целью обобщить правило вывода рассмотренной выше системы, учитывая закон образования цепочек нерегулярного бесконтекстного языка, ука занный вариантами теоремы о развитии [Станевичене 96б], [Станевичене 99] (в



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]