Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
128 6-№AMMAfHKH И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
вспомогательным символом и таких, что из ai в Pi идет путь. Мы можем теперь заменить в нашем рассуждении а и р на ai и pi, и если полное ai-поддерево Т квазипростое, то условие (б') будет выполняться; в противном случае мы заменим он и pi новыми узлами «2 и рг и т.д.; поскольку в этом процессе высоты поддеревьев будут уменьшаться, он рано или поздно оборвется. Итак, наше вспомогательное утверждение доказано.
Пусть теперь L — бесконечный Б-язык. По лемме 4.1 существует Б-грамматика Г = (У, W, /, R) без правил вида Л->Б, A, B^.W, такая, что L(r) = L. Положим p(W) = p, шах | -ф | = gr. В силу лемм 4.4 и 4.5
ЭЛ[Л-»-феЯ]
длина вывода в Г, имеющего простое дерево, не может
gp- 1
превосходить числа • _ t ; в то же время никакую
цепочку w нельзя вывести в Г менее чем за ^w 1 шагов. Поэтому цепочка, длина которой больше
пР — 1
g • g~ir|—г 1» не может обладать в Г простым деревом
вывода. Точно так же заключаем, что если некоторая цепочка и для подходящего ЛеУ имеет (А, и)-дерево
стР+' _ 1
высоты, не превосходящей р -f 1, то | и t—Ь 1.
рР _ J CT0+1 _ 1
Поэтому, положив г = g‘^—~Y -+- 1 и s = g‘ ? }—hU
мы получаем для произвольной цепочки шеЦГ), |ш|>г, представление (1), удовлетворяющее условиям (а), (б), (в).
Следствие. Множество длин цепочек Б-языка либо конечно, либо содержит арифметическую прогрессию.
Из этого следствия вытекает, в частности, что языки примера 13 из § 1.3 и примера 1 из § 3.4 не бесконтекстные.
Приведем примеры применения теоремы 4.5 в случаях, когда следствием воспользоваться нельзя.
Пример 1. Пусть L — язык примера 10 из § 1.3. Если бы L был бесконтекстным, то для всякого достаточно большого k и любого п = 1, 2, ... при подходящих t, xlt х2, У\, г/г» 2, УхУъФ А, мы имели бы akbkak =
§4.31
НЕОБХОДИМЫЕ УСЛОВИЯ ЙЕСКОНТЕКСТНОСТИ
129
— xxyxzy2x2, xxy"zy^x2 = а*ЬгаК Но если в цепочке акЬкак •каждая из подцепочек г/, и у2 состоит только из а или только из Ь, то ни при каком п > 1 цепочка ;cxy"zy%x2 не может иметь вида а*Ь‘а*. Если же, например, ух содержит и а и Ь, то уже цепочка хху2хгу^х2 будет содержать подцепочку вида basb.
Пример 2. Пусть L — язык примера 11 из § 1.3. Для любого k = \, 2, ... имеем a\a\ba\a\^L. Если L — Б-язык, то найдется s > 0 такое, что для любого достаточно большого k и любого п= 1, 2, ... будем иметь при подходящих хь х2, уи у2, z
wl — aJ{abba\a% = xxyxzy2x2, wn = х1У?гУ2х2 e L, |*/,z*/2|<s.
Но если цепочка ytzy2 не содержит вхождений b, то уже w2 не будет делиться вхождением Ь пополам и, значит, не будет принадлежать L. Цепочки ух и у2 не могут содержать Ь, иначе в wn было бы не менее п вхождений Ь. Итак, вхождение b должно содержаться в г; поэтому при k^szs — 1 цепочка ух должна состоять только из а2, а у2 — только из аг. Отсюда w2 — = af ak2+l'bak{+lml, где 1^ = \уу\, l2 = j У21. Но afa*+<1 Ф ф а*+1’а%.
Пример 3. Пусть L = {anbnancm\m, п = 1, 2, ...}. С помощью леммы 4.10 этот пример сводится к примеру 1.
Чтобы сформулировать другой критерий бесконтекст-ности, введем в рассмотрение «-мерные векторы, компонентами которых служат целые неотрицательные числа; для краткости будем говорить просто о векторах. Число п будет все время считаться фиксированным.
Назовем множество векторов М линейным, если существуют векторы <хь ..., as, р (s = 0, 1, ...) такие, что М = {rrixa 1 + • ? ? + msOCs + Р|ти ms = 0, 1, ...}. (Сложение векторов и умножение на число имеют обычный смысл.) Конечную последовательность (ось ... ..., as, р) будем называть базой М. Множество векторов, являющееся объединением конечного числа
5 А. В. ГладкиВ
130 Б-ГРАММЛТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
линейных множеств, называется полулинейным. База полулинейного множества есть, по определению, система баз его линейных слагаемых. Пустое множество также будем считать полулинейным (с пустой базой).
Для произвольного языка L в словаре {аь ..., ап} будем обозначать через K(L) множество векторов
Р„ ?я)|Э*(*€=?&|*|,=А,& ... & \x\n = kn)},
где | х |г означает | х | .
Теорема 4.6. Для любого Ъ-языка L множество K{L) полулинейно и его базу можно найти эффективно по В-грамматике, порождающей L.
Доказательство. Пусть Г = (V, W, /, R) — Б-грамматика и Т — дерево вывоДа в Г. Будем обозначать через М (Т) множество всех тех символов из W, которые встречаются в Г в качестве меток при узлах. Для произвольного M^W рассмотрим множества 51 (М) и 39 (М), состоящие соответственно из всех тех деревьев вывода Т, для которых М(Т) = М, и всех тех цепочек jte V', для которых существуют (/, х)-деревья, принадлежащие 91(М). Положим также S (М) = /((58(М)). Нам достаточно установить, что для каждого Msf множество (5 (М) полулинейно, и указать способ нахождения его базы.
Для М — 0 Утверждение тривиально. Пусть М <=W не пусто и утверждение доказано для всех собственных подмножеств М; докажем его для М.
Будем называть (А, х) -дерево терминальным, если xeV*. Поямым элементарным преобразованием (п. э. п.) терминального (А, х)-дерева Т назовем операцию, переводящую Т в Sub(Т, Т', Т"), где Т' — некоторое простое терминальное полное поддерево Т, а Т" — квазипростое терминальное дерево, содержащее Т' в качестве собственного полного поддерева. Операцию, обратную этой, будем называть обратным элементарным преобразователем (о. э. п.). П. э. п. определяется парой деревьев Г', Т"\ каждому п. э. п. л мы сопоставим вектор X(it), определяемый следующим образом: если Т' есть (В, г)-дерево, а Т" — (В, yizy2) -дерево, то К(п) = (\yiy2\u ???, \у\уг\п). Всевозможных п. э. п. имеется, очевидно, лишь конечное число; мы обозначим их iti,
