Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
НЕОБХОДИМЫЕ УСЛОВИЯ БЕСКОНТЕКСТНОСТИ
131
Для произвольного терминального (/, х) -дерева Т положим к(7') = (Iх, |х|„).
Назовем дерево Т ^%(М) минимальным 1-го рода, если к нему неприменимо никакое о. э. п., и минимальным 2-го рода, если некоторое о.э. п. преобразует его в дерево, не принадлежащее 51 (М). Очевидно, всякое Т е 51 (М) можно получить из некоторого минимального дерева 1-го или 2-го рода последовательным применением п. э. п. Поэтому g (М) представляется в виде {«iA,(ni) -f ... -f «Д(я() -f х(Т) | Т — минимальное дерево 1-го или 2-го рода}. Поскольку число минимальных деревьев 1-го рода конечно, достаточно доказать полули-нейность множества &'(М), отличающегося от (5(М) тем, что в качестве Т берутся лишь минимальные деревья 2-го рода. Но очевидно, что если множество векторов ®i полулинейно, то множество ®2 = {«iai + ... ... + «sas + р|р <=$>!; пи nt = 0, 1, ...}, где аи ... ..., at — заданный набор векторов, также полулинейно, причем базу ®2 можно найти эффективно по базе ®i и векторам он, ..., as. Итак, S (М) будет полулинейным, если таковым окажется множество (5о(М) = {х(Т) \ Т — минимальное дерево 2-го рода}, а поскольку все минимальные деревья 1-го рода и все п. э. п. могут быть построены эффективно, для нахождения базы S (М) достаточно уметь строить базу Ш0(М). Но (50(М) представляется как объединение конечного числа множеств вида {Х,(лО + к (?) IТ <= М'}, где ж — фиксированное п. э. п. и М'— фиксированное собственное подмножество М. Полулинейность такого множества сразу следует из полулинейности (5(АТ), и база его очевидным образом строится по базе б(М').
Замечание. Если словарь одноэлементен, можно отождествлять как цепочки, так и векторы с натуральными числами. Полулинейное множество будет тогда объединением конечного числа арифметических прогрессий и конечного множества. Но такое множество есть Л-язык (пример 3,6) из § 1.3). Таким образом, вся-*? кий Б-язык в одноэлементном словаре автоматный. Сверх того, по Б-грамматике с одноэлементным основным словарем эквивалентная ей /4-грамматика строится эффективно,
5*
132 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
Докажем теперь еще одно утверждение, родственное теореме 4.5; оно особенно пригодится нам в следующем параграфе.
Теорема 4.7. Для любого бесконечного Ъ-языка L найдется такое натуральное число s, эффективно определяемое по порождающей L Ъ-грамматике, что, каковы бы ни были цепочки х, у, z такие, что xyz е L и \у\^ s, цепочку у можно представить в виде у = ij\vy2 так, что v ф А и либо а) цепочка хух представима в виде ху\ =
— ххих2, где X\unx2vny2z^L при любом п = 1, 2, ..., либо б) цепочка y2z представима в виде y2z = Z\WZ2, где xyxvnzxwnz2^ L при любом п= 1, 2, ...
Доказательство. Пусть Г — Б-грамматика, порождающая L, и пусть g и р — соответственно максимум длин правых частей правил* и мощность вспомогательного словаря Г. Положим s = 2 (р -f- 1) • ^2(р+Ч. Рассмотрим цепочку xyz е L такую, что | у \ ^ s. Пусть Т — некоторое дерево вывода этой цепочки в Г и С — соответствующая система составляющих. Поскольку ширина системы С не превосходит g, мы можем по лемме П1.1 найти такие точки ai ^ ^ ap+i < f}pyi sC ... sC pi
цепочки xyz, что [a(, pi], ..., [ap+i, pP+i] eC и либо ai<...<aP+i и ai, ..., aP+i — точки отрезка у, либо pi ;>\.. > Pp+i и Рь ..., pp+i — точки отрезка у. Пусть для определенности имеет место первое. В силу выбора числа р найдутся такие t, j, 1 ^ i ?< / ^ р + 1, что узлы А\ и /4г дерева Т, от которых происходят составляющие [аг-, Pi] и [а,, РД помечены одним и тем же символом В. Обозначим полные Л г и Л2-поддеревья дерева Т через Т\ и Т2 соответственно. Очевидно, Т2 есть поддерево Ть поэтому, если Т\—(В,^)-дерево и Т2 — (В, t2)-дерево, то t2 —- подцепочка t\ и цепочка xyz представима в виде xyz = x'vt2wz2, где vt2w = t\ и отрезки v, t2> w и z2 начинаются в точках a*, a,-, pj + 1 и p, + 1 соответственно (здесь допущена вольность в обозначениях). Поскольку a< < a,j и обе эти точки расположены в отрезке у, для подходящих у\ и г/г имеем y=y\vy2, х'=хуи t2wz2 — y2z\ при этом v Ф А. Если теперь положить Ui = Ti, U„+i — Sub(Un, T2, Г,), то при любом п = = 1, 2, ... Un будет (В, vnt2wn)-деревом, а Тп — = Sub (T,ThUn) будет (/, xy\Vnt2wnz2)-деревом, где I — начальный символ Г, так что xy\Vnt2wnz2^L. Та-
§ 4.3] НЕОБХОДИМЫЕ УСЛОВИЯ БЕСКОНТЕКСТНОСТИ 133
ким образом, положив zt = t2, получаем искомое представление.
Пример 4. Пусть L = {anbnam\rn, п = 1, 2, ...; т ^ п]. Теоремы 4.5 и 4.6 к языку L неприменимы; действительно, требуемое теоремой 4.5 представление цепочки апЬпат получается при х\ = an~l, ух = a, z = А, У2 = Ь, х% — Ьп~1ат, и K(L)={p-(l,l) + q-(2, 1) + -1- (2, 1)|/г, <7 = 0, 1, ...}. В то же время теорема 4.7 позволяет установить, что L — не Б-язык. Именно, если бы цепочка апЬпат, т ^ п, допускала требуемое этой теоремой представление при х = апЬп, у — ат, z = А, то цепочка и или w во всяком случае состояла бы либо целиком из а, либо целиком из Ь; но если бы она при этом была пуста или содержалась в у, то язык L содержал бы любые цепочки вида anbnam+ic, где с > 0 — постоянная и г = 1, 2, ..., а в противном случае в L нашлась бы цепочка вида аРЪчаТ, где р ф q.
