Гладкий - Формальные грамматики и языки - 1973 (947381), страница 26
Текст из файла (страница 26)
е. дерево вывода цепочки х,у",гу"х, в Г. Мы получили, таким образом, представление цепочки в в виде (1), удовлетворяющее условию (в). Выполнение условия (а) вытекает из того, что Г пе имеет правил вида А - В, А, В ее %'. Что касается условия (б'), то оно будет выполняться, если У' — квазипростое дерево (лемма 4.5). Если У' — не квазипростое дерево, то в нем найдутся два различных узла а, н Бь отличных от корня, помеченных одним и тем же Е А. В. Гладкий !йз в-ггайммдтнки н мАшины с мАГАзиннОЙ пАмятью !Гл. 4 вспомогательным символом и таких, что из а! в р! идет путь.
Мы можем теперь заменить в нашем рассуждении а и р на а! и р1, и если полное а1-поддерево Т квази- простое, то условие (б') будет выполняться; в противном случае мы заменим а! и 1!! новыми узлами аг и рг и т. д.; поскольку в этом процессе высоты поддеревьев будут уменьшаться, он рано или поздно оборвется. Итак, наше вспомогательное утверждение доказано.
Пусть теперь 2. — бесконечный Б-язык. По лемме 4.1 существует Б-грамматика Г=(Р', (Р, 1, 22) без правил вида А-Р В, А, Вен !(!Р, такая, что Т. (Г)=Т,. Положим !2(!Р)=р, шах 12р!=у. В силу лемм 4.4 и 4.5 вл !А-РФ н а! длина вывода в Г, име1ощего простое дерево, не может ЕР ! превосходить числа ! ! в то же время никакую ! 1Р ! — ! цепочку гв нельзя вывести в Г менее чем за г шагов. Поэтому цепочка, длина которой больше ЕР д + 1, не может обладать в Г простым де(гевом е — ! вывода. Точно так же заключаем, что если некоторая цепочка и для подходящего А ~ й7 имеет (А, и)-дерево ЕР+! высоты, не превосходящей р + 1, то ~ и !( д, + 1. г~ — ! Р -1- 1 ! Поэтому, положив г=д — +1 и з=у +1, ' д — 1 д †! мы получаем для произвольной цепочки Ге ее Т. (Г), 1ш ~ > г, представление (1), удовлетворяющее условиям (а), (б), (в).
С л е д с т в и е. Множество длин цепочек Б-языка либо конечно, либо содержит арифметическую прогрессию. Из этого следствия вытекает, в частности, что языки примера 13 из з 1.3 и примера 1 из $3.4 не бесконтекстные. Приведем примеры применения теоремы 4.5 в случаях, когда следствием воспользоваться нельзя. Пример 1. Пусть Š— язык примера 10 из $1.3. Если бы 2. был бесконтекстным, то для всякого достаточно большого Ь и любого п = 1, 2, ... при подходящих г, х„хги у„у„г, у,у, ~ Л, мы имели бы а"Ь'а 2 2.2\ неоеходимые услэвия весконтекстности !29 1 1 2 2 = х,у,гу х„х,у"гулх = а'Ь'а'.
Но если в цепочке а"Ь"а каждая из подцепочек у, и у, состоит только из а или только из Ь, то ни при каком п > 1 цепочка х,у",гу,"хг ие может иметь вида а'Ь'а'. Если же, например, у, содержит и а и Ь, то уже цепочка х,у',гу'хг будет содержать подцепочку вида Ьа'Ь. Пример 2. Пусть У. — язык примера 11 из 3 1.3. Для любого Ь=1, 2, ... имеем аааАЬааай~1'.. Если 1'.
— Б-язык, то найдется з > О такое, что для любого ,достаточно большого Ь и любого и = 1, 2, ... будем иметь при подходящих хь х„у„у„г ш = айаАЬалай= х у гу х, г 12 11 22 ге = х,у",гу"х я)., ~у,гуг~ (з. Но если цепочка у,гуг не содержит вхождений Ь, то уже шг не будет делиться вхождением Ь пополам и, значит, не будет принадлежать 1.. Цепочки у, и у, не могут содержать Ь, иначе в и„было бы не менее и вхождений Ь. Итак, вхождение Ь должно содержаться в г; поэтому при й >з — 1 цепочка у, должна состоять только из а,, а у, — только из ао Отсюда и12 = = а",а,'+'Ьал'Р'аг, где !1=~у!~, 1,=1у ~. Но алайчп Ф ~ь а"+пал.
2' П р и м е р 3. Пусть 2. = (а" Ь "а" с'" ~ т, и = 1, 2, ...). С помощью леммы 4.10 этот пример сводится к примеру 1. Чтобы сформулировать другой критерий бесконтекстности, введем в рассмотрение и-мерные векторы, компонентами которых служат целые неотрицательные числа; для краткости будем говорить просто о в ект ор а х. Число и будет все время считаться фиксированным. Назовем множество векторов М лине й н ы м, если существуют векторы а1, ..., а„р (з = О, 1, ...) такие, что М = (т1 221 +... + т а, + р ! т„..., т, = О, 1,,), (Сложение векторов и умножение на число имеют обычный смысл.) Конечную последовательность (а„... ..., аа, р) будем называть б а з о й М.
Множество векторов, являющееся объединением конечного числа ее 1Зо В-ГРАммАтики и мАшины с .ИАГАзиннОи ИАмятью»гл. » линейных множеств, называется п о л у л и н е й н ы м. Б а з а полулннейного множества есть, по определению, система баз его линейных слагаемых. Пустое множество также будем считать полулинейным (с пустой базой). Для произвольного языка Е в словаре (а», ..., а„) будем обозначать через К(Е) множество векторов ((й», ..., йл) (:-)х (х ен Е 8» ( х 1, = й, й ... й ) х ), = й„)), где (х 1, означает (х ! .
л»' Теорем а 4.6. Для любого Б-языка Е множество К(Е) полулинейно и его базу можно найти эффективно по Б-грамматике, порождающей Е. Доказательство. Пусть Г=(1»,%',1,)1)— Б-грамматика н Т вЂ” дерево вывода в Г. Будем обозна- чать через М(Т) множество всех тех символов из Ч7, которые встречаются в Т в качестве меток при узлах. Для произвольного М»:-)У" рассмотрим множества 5(М) и 6(М), состоящие соответственно из всех тех деревьев вывода Т, для которых М(Т) = М, и всех тдх цепочек х~ )н, для которых существуют (1, х)-лере»(( я, принад- лежащие 5(М).
Положим также 6(М) = К(Е(М)). Нам достаточно установить, что для каждого М ~ Чу множество 6(М) полулинейно, н указать способ нахо- ждения его базы, Для М = уз )»тверждение тривиально. Пусть Мы (Р' не пусто н утверждение доказано для всех собственных подмножеств М; докажем его для М. Будем называть (А, х) -дерево терминальным, если хеппиl'. Поямым элементарным преобразованием (п. э. п,) терминального (А, х)-дерева Т назовем операцию, пере- водящую Т в ЬцЬ(Т, Т', Т"), где Т' — некоторое простое терминальное полное поддерево Т, а Т" — квазипростое терминальное дерево, содержащее Т' в качестве соб- ственного полного поддерева. Операцию, обратную этой, будем называть обратным элементарным преобразовате- лем (о. э.
п.). П. э, п. определяется парой деревьев Т', Т"; каждому п. э. п. и мы сопоставим вектор Л(п), опреде- ляемый следующим образом; если Т' есть (В, е)-дерево, а Т" — (В, у»гуг)-дерево, то Л(Г») =((у»уе»»», ..., (у»у») ). Всевозможных п. э. п. имеется, очевидно, лишь конечное число; мы обозначим их пь ..., и». э »гй неОБхОДИмые услОВия БескОнтекстности ци Для произвольного терминального (1, х)-дерева Т положим х(Т) = ((х)», ..., (х( „). Назовем дерево Т ее 6(М) минимальным 1-го рода, если к нему неприменимо никакое о.
э. п., и минимальным 2-го рода, если некоторое о. э. п. преобразует его в дерево, не принадлежащее 5(М). Очевидно, всякое Т ее Я(М) можно получить из некоторого минимального дерева 1-го или 2-го рода последовательным применением и. э. п. Поэтому 6 (М) представляется в виде (п,Л(п»)+... + п»Л(п»)+ х(Т) (Т вЂ” минимальное дерево 1-го или 2-го рода). Поскольку число минимальных деревьев 1-го рода конечно, достаточно доказать полулннейность множества 6'(М), отличающегося от 6(М) тем, что в качестве Т берутся лишь минимальные деревья 2-го рода. Но очевидно, что если множество векторов 6Я» полулннейно, то множество ЯЯЕ = (п»а»+...
...+па+р(рееЗ», и», ..., п»=0, 1, ...), где а», ... ..., ໠— заданный набор векторов, также полулинейио, причем базу Жз можно найти эффективно по базе Ж» и векторам а», ..., а,. Итак, 6(М) будет полулинейным, если таковым окажется множество 6Е(М) = (и(Т) ) Т— минимальное дерево 2-го рода), а поскольку все минимальные деревья 1-го рода и все п. э. п. могут быть построены эффективно, для нахождения базы 6(М) достаточно уметь строить базу 6»»(М). Но 6е(М) представляется как объединение конечного числа множеств вида (Л(п»)+н(Т) ~ТБЕМ'), где и» вЂ” фиксированное п.
э, п. н М' — фиксированное собственное подмножество М. Полулинейность такого множества сразу следует нз полулинейности 6(М'), и база его очевидным образом строится по базе 6 (М'). 3 а м е ч а и и е. Если словарь одноэлементен, можно отождествлять как цепочки, так и векторы с натуральными числами. Полулинейное множество будет тогда объединением конечного числа арифметических прогрессий и конечного множества.
Но такое множество есть А-язык (пример 3, б) нз $1.3). Таким образом, всякий Б-язык в одноэлементном словаре автоматный. Сверх того, по Б-грамматике с одноэлементным основным словарем эквивалентная ей А-грамматика строится эффективно, 132 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ 4ГЛ. 4 4 4Л! НЕОБХОДИМЫЕ УСЛОВИЯ ББСКОНТБКСТНОСТИ 433 Докажем теперь еще одно утверждение, родственное теореме 4.5; оно особенно пригодится нам в следующем параграфе. Т е о р е м а 4.7.
Для любого бесконечного Б-языка Е найдется такое натуральное число з, эффективно определяемое по порождающей Е Б-грамматике, что, каковы бы ни были цепочки х, у, г такие, что хуг еп Е и ]у] ) з, цепочку у можно представить в виде у = д4оут так, что о чь Л и либо а) цепочка ху, представима в виде ху4 —— = х,их,, где х,и'хуо"утг ен Е при любом и = 1, 2, ..., либо б) цепочка утг представима в виде узг = г4п4гт, где ху,о"г4п4"гте= Е при любом и = 1, 2, ... До к а за тельство. Пусть à — Б-грамматика, порождающая Е, и пусть у и р — соответственно максимум длин правых частей правил и мощность вспомогательного словаря Г.
Положим з = 2(и+ 1) АКР+'!. Рассмотрим цепочку хуг е= Е такую, что ]у] > з. Пусть Т— некоторое дерево вывода этой цепочки в Г и С вЂ” соответствующая система составляющих. Поскольку ширина системы С не превосходит д, мы можем по лемме П1.1 найти такие точки а4 ( ... = ар+4 ( арте «-... ( Р4 цепочки хуг, что [и4, Щ, ..., [ар4.Ь рр+4] 4н С и либо 4х4 ... ( ар+4 и аь ..., арэ4 — точки отрезка у, либо Р4 ) .) 5р+4 и 54, ..., рр4.4 — точки отрезка у.
пусть для определенности имеет место первое. В силу выбора числа р найдутся такие 4', 1, ! ( 4 (1 = р+ 1, что узлы А, и Ат дерева Т, от которых происходят составляющие [а4, р4] и [иь рь], помечены одним и тем же символом В, Обозначим полные А,- и Ат-поддеревья дерева Т через Т, и Тт соответственно. Очевидно, Тт есть поддерево Т,; поэтому, если Т1 — (В,14)-дерево и Тг — (В, (т)-дерево, то гт †надцепоч 1~ и цепочка хуг представнма в виде хУг = х'о(тгвгь где О1тв = 14 и отРезки о, 1ь п4 и г, начинаются в точках а4, аь р; + 1 и 54 + 1 соответствен. но (здесь допущена вольность в обозначениях).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
