Гладкий - Формальные грамматики и языки - 1973 (947381), страница 41
Текст из файла (страница 41)
Теперь нам достаточно показать, что если à — приведенная Б-грамматика и в графе ()л () )Р'; Я) есть циклы, то в деревьях полных выводов найдутся сколь угодно длинные отмеченные пути. Пусть символ А принадлежит какому-либо циклу указанного графа. Тогда для некоторой цепочки со ен ( к'() )Г)+ найдется (А,ьт)-дерево Т~ в Г, в котором'"' из корня идет отмеченный путь в висячий узел, помеченный тем же символом А. Для и = 2, 3, ... положим Т„= = БИЬ(Т вЂ” и То, Тс), где То — единичное дерево с меткой А в единственном узле. При достаточно большом и дерево Т будет содержать сколь угодно длинный отмеченный путь из корня в висячий узел с меткой А. Поскольку грамматика Г приведенная, найдется дерево полного вывода Т, в котором некоторый узел а имеет метку А.
По предыдущему в полном а-поддереве Т' дерева Т нз корня исходит хотя бы один отмеченный путь. Полагая Т„' = БИЬ(Т„, Т,, Т'), видим, что в Т'„ из корня идет отмеченный путь, более длинный, чем в Т., уже в узел, помеченный основным символом; но ввиду приведенности Г дерево Т', можно «достроить» до дерева полного вывода. Из лемм 6,1 и 6.2 и из того очевидного обстоятельства, что свойство ограниченности ширины сохраняется при сильной эквивалентности, немедленно вытекает Теорема 6.5.
а) Для всякой Д-грамматики ограниченной шириньл можно построить сильно эквивалентную ей простую Д-грамматику. 6) Если для Д-грамматики 0 существует сильно эквивалентная ей простая Д-грамматика, то ст' имеет ограниченную ширину. Посмотрим теперь, для каких Б-грамматик существуют эквивалентные в том или ином смысле простые Д-грамматики, или, что то же самое, Д-грамматики ограниченной ширины. Ясно, прежде всего, что удлиняющая Б-грамматика тогда и только тогда вкладывается в простую Д-грамматику (и притом эффективно ь) ), когда правая часть каждого ее правила содержит вхождения основных символов. Поэтому из теоремы 6.2 следует, что для всякой Б-грамматики можно построить слабо эквивалентную ей простую Д-грамматику. Чтобы исследовать вопрос о сильной эквивалентности, введем следующее понятие.
Пусть Г = (У, )«, т', )т) — Б-грамматика. Будем сопоставлять символам из У 0 %' числа, которые назовем их степе н я м и, следующим образом: (1) степени основных символов, и только их, равны нулю; (В) пусть для каждого й = О, ..., и — 1 определено понятие символа степени й; тогда символу А приписывается степень и, если ему не приписано в качестве степени ни одно из чисел О, ..., и — 1 и правая часть каждого правила с левой частью А содержит хотя бы одно вхождение символа степени, не превосходящей п — 1.
Символы, которым с помощью такой процедуры никакая степень не приписывается, считаем имеющими бесконечную степень. Наибольшая из степеней символов полного словаря Г будет называться степенью грамматики Г. ') То есть для 6-грамматики Г можно построить простую Гс-грамматику вида (Г, 1). ЕОЗ ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О В.ГРАММАТИКАХ [ГЛ, б $ ьл[ СИСТЕМЫ УРАВНЕНИИ. В ЯЗЫКАХ Ясно, что степень каждого символа, а значит, и степень грамматики можно найти эффективно.
Так, грамматики со схемами 11-+С1,!-~аСЬ, 1- аЬ, С-+ аСЬ,С- аЬ), (1-+С1,1 — аСЬ, 1-+аЬ, С вЂ” АСВ, С- аЬ, С-ь ааЬЬ, А-+аа, В -+ЬЬ) и (1 — 11, 1-+а!Ь, 1 — э аЬ) ИМЕЮТ СООтнстетВЕННО СТЕПЕНИ 2, 3 И Оь (ХОтя ВСЕ ОНИ эквивалентны). Легко заметить (ср. доказательство теоремы 6.2), что если à — приведенная удлиняющая Б-грамматика, то ее степень равна точной верхней границе степеней систем составляющих, отвеча[ощих деревьям полных выводов в Г.
Поэтому, если назвать Б-грамматики Г[ и Гт сильно эквивалентными в случае, когда они эквивалентны и множества систем составляющих, отвечающих деревьям полных выводов в Г4 и Гы совпадают, то будет справедлива Л е и и а 6.3. Если двг приведенные удлиняющие Б-грамматики сильно эквивалентны, то их степени равны. Нам понадобится также Л ем м а 6.4. Для всякой Б-грамматики конечной степени можно построить сильно эквивалентную ей удлиняющую Б-грамматику конечной степени.
Доказательство, весьма простое, предоставляется читателю (ср. доказательство леммы 4.1 и упражнение 4.1). Связь понятия степени с Д-грамматикамн видна из следующей леммы. Л е м м а 6.5, Приведенная удлиня>ощая Б-грамматика тогда и только тогда вкладывается в Д-грамматику без циклов (и притом эффективно), когда ге степень конечна. Д о к а з а т е л ь с т в о. а) Пусть степень Б-грамматики Г конечна, А — ь[ — произвольное правило Г и степень А равна и. Объявим отмеченными все вхождения в [ь символов степеней, не превосходящих и — 1, Ясно, что полученная так Д-грамматика не будет иметь циклов.
6) Если Д-грамматика ((У, В',1, 14),[) не имеет циклов и наибольшая длина пути в графе (Р О И[4; Я) равна Ь, то степень каждого символа и ее У 1) !Р не превосходит наибольшей длины 1[ пути в графе (У1) %', Я), исходящего из узла с меткой а (доказывается очевидной индукцией по Ь„). Поэтому степень грамматики (У, %',1, 14) не превосходит И. Из лемм 6.1, 6.3, 6.4, 6.5 непосредственно вытекает Теорем а 6.6.
а) Для всякой Б-грамматики конечной степени можно построить сильно эквивалентную ей простую Д-грамматику. 6) Если для приведенной удлиняющей Б-грамматики Г существует сильно эквивалентная гй простая Д-грамматика, то степень Г конечна. 3 а и е ч а н и я. 1. Сопоставляя конец доказательства леммы 6.5 с леммой 6.2 (пункты б) и в)), видим, что если 6 = (Г,[) — Д-грамматика ограниченной ширины, то степень Г не превосходит ширины О. Отсюда по лемме 6.3 вытекает, что если à — приведенная удлиняющая Б-грамматика, то ширина Д-грамматики, сильно эквивалентной Г, не может быть меньше степени Г.
2. Характеристикой Д-грамматики, в известном смысле двойственной ширине, является ее вы с от а— максимум высот соответствующих деревьев подчинения. Если такой максимум существует, естественно сказать, что Д-грамматика имеет ограниченную высоту. О возможности построения сильно или слабо эквивалентной Д-грамматики ограниченной высоты для данной Б-грамматики см. упражнение 7.7. й 6.4.
Системы уравнений в языках. Формальные степенные ряды Сейчас мы покажем, что ОБ-грамматики можно интерпретировать как своеобразные системы уравнений, в которых коэффициентами и неизвестными являются языки. Такой интерпретацией, вернее, подсказываемым ею способом записи, особенно охотно пользуются специалисты по языкам программирования. Фиксируем словарь У = (а[...,, а ) и конечный набор переменных Е = ($н ..., $,).
Рассмотрим и много- членов от этих переменных, или, как мы будем здесь говорить, н е и з в е с т н ы х, с коэффициентами, представляющими собой непустые конечные языки в словаре )т: 11(е[, ..., $,)...„1 ($[, ..., $,). (Не требуется, СИСТЕМЫ УРАВНЕНИЙ В ЯЗЫКАХ 2!! 6 ел) 2!О ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ О В ГРАММАТИКАХ [ГЛ. 6 Покажем, что для любого ! = О, 1, ... язык Е) ~ есть множество цепочек в У, выводимых в Г из $т с помощью деревьев вывода высоты, не превосходящей !+1. Действительно, пусть утверждение доказано для всех 1=0, ..., !е и всех 1=1, ..., л.
Но й'е+')= (в +н = ! ф'е), ..., 1(ге)) — это множество Всех тех цепочек, котоРые полУчаютсЯ из членов 1я если подставлЯть в них вместо $1 цепочки из х.(1'е), вместо $т — цепочки из св(') и т. д. (причем разные вхождения одного и того же $) — даже в один член — могут замешаться разными цепочками). Будем теперь в произвольные деревья высоты 1, имеющие внд 4 Г~ и)' '' 'Схз где а, ... а, — член );, подставлять вместо каждого вхождения каждого $г, !'=1, ..., и, какое-либо ф, г)- дерево грамматики Г, имеющее высоту, меньшую или равную !е, и такое, что г ее У'. Полученное множество деревьев обозначим Мг,п По предыдущему множество (Пру ц (Т) ! Т ен Мх,!) есть как раз Е.т("+').
Однако Мь!— это множество ($п к)-деревьев в Г высоты, не превосходящей !е+ 1, таких, что х ~ У". Итак, наше утверждение доказано. Из установленного в предыдущем абзаце факта немедленно вытекает, что (.т (Г) = Е! для любого 1' = 1, ..., п. Упомянем еще об одном способе представления наименьшего решения нормальной системы уравнений — с помощью так называемых формальных степенных рядов. Фиксируем некоторый пересчет цепочек в алфавите У: хе, хь ..., х„..., в котором более короткие цепочки предшествуют более длинным, так что, в частности, хе = Л. Фиксируем также некоторую функцию !(и), определенную на натуральном ряду и принимающую в качестве значений натуральные числа.
Выражеч ние,~з ~(п)х„, или, иначе, ~(0)хе+~(1)х, + ... +1(п)х„+ будем называть неком мутативным ф ор м ал ьн ы м с те и е иным рядом (или для краткости просто формальным рядом) в алфавите У. Множество (х~ ) ~(!) ) 0) назовем опор н ы м м н о ж е с т в о м данного формального ряда. Многочлен без переменных, коэффициентами которого служат цепочки в У, можно рассматривать как частный случай формального ряда, если заменить в нем знак () знаком +, расположить члены соответствующим образом и «привести подобные». Для заданной конечной последовательности натуральных чисел р = (ле, ль ..., Йч) будем обозначать через )хр множество всех формальных рядов в алфавите У, у которых коэффициенты при хе, хь, хл равны пе, пь ..., лм соответственно. (В частности, последовательность р может быть пустой — тогда )ср есть множество всех формальных рядов в У.) Если считать окрестностями ряда г множества Яр,, )хрп ..., )хр„, ..., где рм — последовательность первых М+ 1 коэффициентов г, то множество всех формальных рядов в словаре У становится топологическнм пространством.
Сходнмость в этом пространстве означает, очевидно, следующее: последовательность рядов гь ..., г„, ... сходится к ряду г, если для каждого Лг = О, 1, ... найдется такое 5 = 1, 2, ..., что для любого з = 8, 5+ 1, ... имеют место равенства: ).(0) = !(0), 1,(1) = )(1), ..., )„(Лг) = =1(М), где (х(л) и 1(и) означают коэффициенты пРи х„в рядах г, и г, соответственно.
Легко убедиться, что если последователыюсть рядов гь ..., г„... сходится к ряду г, то опорное множество г является пределом последовательности опорных множеств гь ..., г„... «). Вернемся теперь к системе уравнений (е), наложив на нее некоторые ограничения, а именно: (1) левые части уравнений не должны содержать членов вида (2) ни один из многочленов ~! не должен содержать *) Множество М называется верхним !нижним] пределом последовательности множеств, если М есть множество всех элементов, принадлежащих бесконечному числу членов последовательности (соответственно всем членам последовательности, кроме, быть может, конечного их числа). Если верхний предел совпадает с нижним, ен назынается пределом последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
