-Л [С, Е]

S[B, Е]

Мы утверждаем, что Р распознает язык {а"Ь"\пО}. Можно показать индукцией по п, что S.=+ {a"b" t х, s) и С=>+ (a"6"+i х, s) для всех л; и п. Например, для входной цепочки ааЬЬ

A=y(tbb,n Е=>ЩЬЬ, S)

(-t ЬЬ, 5) B={btb,s) С=фЧЬЬ,5) A={a\bb,s) S{ab\b, s) B=:>HbUs) СЦаЬЬи s) Л =ф-1 (л t bb, s) S:={anbbl s) □

(7) (8)

X А

В, Е] К, Е]

Правила (7), (8), (1), (й) и (4) точно соответствуют аналогичным правилам примера 6.4. Правило (6) гарантирует, что распознает цепочку, состоящую нз цепочки, распознаваемой нетерминалом Л (это будет О"!"), за которой следует символ 2. Заметим, что Л всегда приводит к успеху, так что правило для 5i могло бы иметь вид 5-Л[7, tt] для любого W.

Далее, надо написать правила, распознающие цепочку вида О", за которой следует 12 для некоторого /*. Для этого достаточно взять

(9) (10) (И)

5,-€ -D -

-X У -С

5„С1 Я, Е]

Правила (10), (II), (2), (3) и (4) соответствуют аналогичным правилам примера 6.4, причем С распознает 12 Правило для 5 работает так: пока на входе идет префикс, состоящий из ну-

Приведем теперь пример ОЯНРОВ-программы, определяющей не контекстно-свободный язык.

Пример 6.5. Построим ОЯНРОВ-программу, распознающую язык {0"1"2« 1}. Из примера 6.4 мы. знаем, как написать правила, проверяющие, начинается ли в данной цепочке с некоторого места цепочка 0"1" или 1"2". Наша стратегия будет состоять в том, чтобы сначала проверить, что входная цепочка имеет префикс вида 0°1°2 для тО. Если нет, то мы сделаем так, чтобы входная цепочка не была допущена. Если да, то произойдет неудачный промежуточный вызов, который заставит рассмотреть входную цепочку сначала. Затем проверим, имеет ли она вид 012Л Такнм образом, входная цепочка выдержит оба этн испытания тогда и только тогда, когда она имеет вид 0"1"2" для п> 1.

Нам нужны нетерминалы, распознающие один терминал или сразу приводящие к успеху или неудаче. С них начнем список правил:

(I) ХО (2)

(3) Z2

(4) Е-е

(5) F-f

Программу из примера 6,4 приспособим для распознавания цепочки 0"1"2 нетерминалом 5j. Соответствующие правила таковы:

(6) Si-A[Z,Z]

Определение. ОЯ[РОВ-программой назовем четверку Р= (N,2,>, 5), где N, 2 те же, что и в ЯНРОВ-программе, а R- список правил (операторов) вида А->B[C,D], А-и А- Здесь А, В, С п D принадлежат N, aZ\j{e} и /-метасимвол, означающий неудачу, как и в ЯНРОВ-программе. Для каждого А есть не более одного правила, в котором А стоит слева от стрелки.

Определим для ОЯНРОВ-программы отношения =Ф": ,

(1) Если для А есть правило А-а, где a\j{e}, то А= (afiiy, s) для всех шХ* и A=t>{\w, f) для всех 2*, у которых нет префикса а.

(2) Если для есть правило А-то Az={\w, f) для всех НУ 2*.

(3) Если для А есть правило АВ[С D], то

(а) mB{w\xy, S) иС=Ф"(л1/, s) следует Л =« + «+i([iijct/,s).,

(б) из Й=ф" (йул;, s) иС=ф"(л;, f) . следует Л =ф"+"+1 (йул;, f).

(в) ш B="*(\wx, f) и D =Ф" (nyfjt, s) следует Л =°+"+i(i«jf;,s),

(г) из B:={\w,f) и £)=Ф"(ш,/) следует Л =Ф«+"+ (toy,/).

Будем писать Л + (л; f 1/, г), если Л =ф« (jy; f , г) для некоторого /г> 1. Языком, определяемым программой Р, назовем язык L{P)={w\S{w\, s)}.

Пример 6,4. Пусть P - i-va ОЯНРОВ-программа с правилами

Лемма 6.4. Пусть Если Л =Ф+ (х f у, fj) и yv и г = г.

P = (N, 2, R, 8)~-ОЯШОВ-программа, Л =Ф+(п f и, Га), где xy=uv, то х = и.

Доказательств о. Упражнение. □

Теперь докажем две теоремы об ОЯНРОВ-программах. Первая говорит о том, что класс языков, определяемых ЯНРОВ-программами,содержитсявклассе языков, определяемых ОЯНРОВ-программами. Вторая утверждает, что каждый язык, определяемый ОЯНРОВ-программой, распознается за линейное время подходящей машиной с произвольным доступом к памяти.

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

Теперь нужно соединить программы для 5j и S. Сначала введем нетерминал Sg, который сам не распознает никакой входной цепочки, т. е. никогда не меняет положение входного указателя, но приводит к успеху или неудаче тогда, когда 5 приводит Соответственно к неудаче- или успеху. Правило для таково:

(12) S,-SdF,E]

Заметим, что если приводит к успеху, то Sg вызывает нетерминал F, который сообщает о неудаче и возвращает входной указатель туда, где был вызван S. Если 5j терпит неудачу, то Sg вызывает иетерминал который сообщает об успехе. Таким образом, Ss в любом случае не „потребляет" входную цепочку. Теперь введем начальный символ 5 с правилом

(13) SS,[F,S,]

Если 5i приводит к успеху, то S сообщает о неудаче, и S, вызывается в начале входной цепочки. Поэтому 5 приводит к успеху тогда, когда Si и S приводят к успеху для одной и той же входной цепочки. Если 5 приводит к неудаче, то Sg сообщает об успехе, так что 5 приводит к неудаче. Если S сообщает об успехе, а S-o неудаче, то S тоже сообщает о неудаче. Таким образом, эта программа распознает язык {0"12" п > 1}, представляющий собой пересечение множеств, распознаваемых нетерминалами S и Sg. Следовательно, существуют не контекстно-свободные языки, определяемые .ОЯНРОВ-программами.. То же, кстати, верно и для ЯНРОВ-программ (см. упр. 6.1.1). □

Изучим некоторые свойства ОЯНРОВ-программ. Справедлива лемма, аналогичная лемме .1:

Теорема 6.2. Каждый язык, определяемый ЯНРОВ-программой, определяется ОЯНРОВ-Лрограммой.

Доказательство. Пусть 1 = 1 {Р) для-ЯНРОВ-програм-мы Р= (N, 2, 5). Возьмем ОЯНРОВ-программу P = (N,S, R,S). где R определяется так:

(1) Если правило Л-е принадлежит R, то оно включается bR.

(2) Если правило А-*-а принадлежит R, то оно включается в R,

(3) Если правило A~~>-f принадлежит R, то оно включается в R\

(4) Вводятся новые нетерминалы Е, F и в R включаются правила Ее и F-f. (Заметим, что другие нетерминалы с такими же правилами можно отождествить с этими.)

(5) Если А-уBC/DR, то в R включаются правила

A~~A[E,D] AB[C,F]

где Л.-новый нетерминал.

Пусть -это N вместе со всеми новыми нетерминалами, введенными при построении R\

Элементарное наблюдение показывает, что если В и С при-. водят к успеху, то Л приводит к успеху, а в противном случае Л сообщает о неудаче. Таким образом, Л приводит к ус-пеху тогда и только тогда, когда Л приводит к успеху (т. е. В и С сообщают об успехе) или Л терпит неудачу (т. е. В терпит неудачу, или В приводит к успеху, а С-к неудаче), а D приводит к успеху. Легко также проверить, что нетерминалы В, С и D вызываются программой Р в тех же точках входной цепочки, в которых они вызываются программой Р. Так как непосредственно моделирует каждое правило из R, то 5= (м/f, s) тогда и только тогда, когда (и, s), и, значит, L(P)=

Е{Р). □

По-видимому, ОЯНРОВ-программы могут в смысле распознавания делать больше, чем ЯНЮВ-программы. Например, легко написать ОЯНРОВ-программу, моделирующую оператор вида

A-BCI(D„D,)

в котором £>j должен вызываться тогда, когда В терпит неудачу, а тогда, когда В приводит к успеху и С-к неудаче. Но

вопрос о том, образуют ли языки, определяемые ЯНРОВ-про-граммами, собственный подкласс класса языков, определяемых >iJiPOB-nporpaMMaMn, остается открытым.

ложить tijf. (Так как „12, то A.afR.)

(3) Повторять шаг (4) для 1:1, 2, k, пока t-j не перестанут меняться.

(4) Пусть правило для Л- имеет вид ->-Ар[А,Аг] и элемент tj еще не определен:

(а) если t„j = f и tj.f = x, положить tij = x, где х-число или f,

(б) если ipjrriy и t.,==mфf, положить Ь.тт

(в) если ipjm и (у+,) = Л положить ,7 = /.

Во всех остальных случаях с t ничего не делать. □

Теорема 6.3. Алгоритм 6.2 правильно определяет tij.

Так же, как и предыдущий язык, можно сделать ОЯНРОВ более выразительным, введя расширенные операторы (см. упр. 6.1.12). Например, каждый расширенный ЯНРОВ-onepaToj) можно рассматривать как расширенную форму ОЯНРОВ-опе-ратора,

6.1.4. Временная спо>кность ОЯНРОВ-языков

Главный результат этого раздела состоит в том, что успешный процесс распознавания входной цепочки ОЯНРОВ-програм-мой (а следовательно, и ЯНРОВ-программой) можно промоделировать за линейное время на автомате, подобном машине с произвольным доступом к памяти. Соответствующий алгоритм напоминает как алгоритм Кока-Янгера -Касами, так и алгоритм Эрли из разд. 4.2, но входную цепочку он обрабатывает в обратном направлении..

Алгоритм 6.2. Распознавание ОЯНРОВ-языков за линейноевремя.

Вход. ОЯНРОВ-программа P=(N, 2, 5), где N-{Лi, Л, Л} и 5 = Л и входная цепочка waa.. из 2*. Предполагается, что a„+i -$-правый концевой маркер.

Выход. Матрица [tij] размера йх(я+1). Каждый ее-элемент либо не определен, либо это целое число т [Отп], либо символ, неудачи /. Если tij-m, то Л,.=ф+ (/Gy+i.. .a+.i-t j+m---a„, s). Если t-j-f, то Л=+ [j aj.. .a„, f). В остальных случаях ие определен.

Метод. Матрицу [tj] будем вычислять следующим образом. Вначале все ее элементы не определены.

(1) Делать шаги (2)~(4) для /=/г+1, я, 1.

(2) Для каждого 1</й если в R есть правило Л,--*jF., положить tij~f\ если в R есть правило Л,-->-е, положить .=0; если Л;-)-й;у, положить ,/ = 1 и, если Л-для Ьфа, по-

Доказательство. Мы утверждаем, что после выполнения алгоритма 6.2 для входной цепочки т = ау,..а„ будет tif~f тогда и только тогда, когда Л,=Ф+(fly.. /), и tij-m .тогда и только тогда, когда Л=Ф+(Яу.. .fly+„i f fly + „.. .fl„, s). Прямая индукция по порядку, в котором вычисляются элементы ,-у, по казывает, что когда элемент получает значение, оно именно то о котором сказано выше. Обратно, индукция по / показывает что если Л,.=(Ау.. .а„, f) или Л;= («у.. .fl/+ i t fly.. .а„, s) то tfj получает значение f или т соответственно. Элемент tj остается неопределенным, если вызов А в позиции ; не закан чивается. Детали доказательства оставляем в качестве упраж нения. □

Заметим, что а.. .aLiP) тогда и только тогда; когда tyi = n.

Теорема 6.4. Для каждой ОЯНРОВ-программы cyuicmeyem такая константа с, что для входной цепочки длины п 1 алгоритм 6.2 тратит не более сп элементарных шагов, причем эти элементарные шаги того же типа, чпю и в алгоритме 4.3.

Доказательство. Суть доказательствав том, чтобы заметить, что на шаге (3) мы проходим по всем нетерминалам не более k раз для любого данного /. □

В заключение отметим, что по матрице, вычисленной алгоритмом 6.2, можно для допускаемых входных цепочек строить древовидные синтаксические структуры, подобные тем, что строились алгоритмом 6.1 для ЯНРОВ-программ. Кроме того, алгоритм 6.2 можно модифицировать так, чтобы он работал (распознавал и анализировал) для обычной, а не для обобщенной ЯНРОВ-программы.

Пример 6.6. Пусть P = (N, 2, R,, Е), где N = {£, Т, Г„ F, F\X,Y,P,M, А, E,R\, = {a, (,), исостоит из правил