Гладкий - Формальные грамматики и языки - 1973 (947381), страница 25
Текст из файла (страница 25)
д. Этот процесс когда-нибудь оборвется, так как на каждом шаге мощность вспомогательного словаря уменьшается. Поскольку язык 1.(Г) не пуст, в описанном процессе никогда не будет выброшен начальный символ, и в конце концов получится приведенная грамматика, эквивалентная Г. Будем теперь называть вспомогательный символ Б-грамматики ц и к л и ч е с к н м, если он зависит от самого себя. Имеет место Л е м м а 4.9, Приведенная Б-грамматика без правил вида А - В, где А и  — вспомогательные с мволы, тогда и только тогда порождает бесконечный язык, когда хотя бы один ее вспомогательный символ является циклическим. Д о к а з а т е л ь с т в о.
! ) Пусть à — данная грамматика и А — циклический вспомогательный символ. Тогда ') Символ, неустрвнииый в старой грамматике, может стать стрвнниыи в новой. Например, в грамматике Г = ((а), (1, А, В), , (1-ьа, 1- АВ, А - а)) устрянииыи символом является только В, нп после изъятия этого сиивелв н правила 1-ъАВ символ А тоже ствнпвнтся устйвпиыыы 124 З.ГРАммАтики и мкшины с ИАГАзиннОЙ пАмятью 1Гл, 4 существуют такие цепочки 4р и ф что А )-уА4р, откуда Г для любого и = 1, 2, ...
имеет место А )-~р"А4р". В выг воде цепочки 4ГАф нз А применяются правила, содержа- щие в правых частях вспомогательные символы; но длины правых частей таких правил больше единицы. Поэтому 4ь4р Ф Л. Поскольку грамматика Г приведенная, при А ~ 7 (! — начальный символ) найдутся такие це- почки й и Гь что 1 ! — ЗА4). Кроме того, найдутся такие г цепочки г, и, о, х, у в основном словаре, что А 1- г, г ф)эаи, Зг)4ыо, $)гях, 41~у фв означает «выводима г г г г г в Г из или совпадает с»), причем ио Ф Л.
Поэтому при любом и = 1, 2, ... из 1 будет выводима цепочка ш„= хи"го"у (так при А чь Т, при А =! имеем вместо этого цепочку и"го"), и при п4 ~,пз цепочки Гв„, и в„, различнь4. 2) Если в грамматике нет циклических вспомогатель- ных символов, то все деревья выводов просты, и их число, а тем более число выводимых из начального символа цепочек, конечно, Т е о р е м а 4.2. Существует алгоритм, позволяющий по любой Б-грамматике Г распознать, является ли язык 4'. (Г) конечным. Доказательство. В силу леммы 49 для вы- яснения вопроса о конечности языка 4'.(Г) достаточно перестроить Г в соответствии с леммами 4.1 и 4.8, а за- тем проверить все вспомогательные символы на циклич- ность (лемма 4.6). Л е м м а 4.10. Для любой Б-граг4натики Г = =(У, Ч7, ), )Г) и любого словаря с «=.
У' можно построить Б-грал4яатику, порождающую язь4к Прям(Г) — (Л). Доказательство. В силу леммы 4.3 мы можем считать, что à — стандартная бинарная Б-грамма- тика. Назовем символ А ен (у исчезающим, если он не является ( у' — х) -бесплодным. Положим Г' = = (х, 1«', Т, %4 () Вз), где В4 получается нз В изъятием правил вида А- а, а4йЕ, а )Гз состоит нз всевозмож- ных правил вида А-+В таких, что для некоторого исче- зающего символа С схема )Г содержит правило А -+ВС или А -+ СВ, Покажем, что Г' — нужная грамматика, $4.п РАспОзнАВАния пустОты и кОначности в-языкА !аз а) Пусть хек 1.(Г').
Тогда, заменив в произвольном выводе цепочки х из 1 в Г' каждое применение правила вида А- В, А, В ~ йг, применением соответствующего правила А- ВС или А- СВ, мы получим вывод в Г, заканчивающийся некоторой цепочкой вида х,С4хрСА ... ... х4С4х4+ь где Сь ..., С4 — исчезающие символы и х4 ... х4+4 = х. Из нее, в свою очередь, можно вывести в Г цепочку вида х4и4хзиг ... х,и4х4»ь где иь ..., и4еи ~(!à — 2)*; но проекция такой цепочки на с есть х.
Итак, х~Прх Т. (Г), а поскольку Л ~ В(Г'), имеем также хек Прхй(Г) — (Л). б) Пусть хек Прзй(Г) — (Л). Рассмотрйм цепочку у ~ 1.(Г) такую, что Прху = х, и де- Р ево Т некоторого вывода цепочки у в Г. Выбросим из Т е злы, обладающие тем свойством, что все «последние все у еся потомки» данного узла А (т. е. потомки, являющи висячими узлами) помечены символами из )à — л, но среди «последних потомков» узла, подчиняющего А, некоторые помечены символами из л, а также всех потомков узлов, обладающих этим свойством.
Ясно, что, - ервых при этом будут выброшены все те и только те узлы, среди «последних потомков» которых ни д о ин не помечен символом из Е, а поэтому на висячих узлах полученного дерева будет «написана» в точности цепочка х; во-вторых, полученное дерево будет деревом некоторого полного вывода в Г'. Итак, х ~ Т.(Г').
Выведем из доказанной леммы следующее любопытное утверждение. Будем называть грамматику Г =()г, (Р,/, В) об общенной Б-грамматикой (ОБ-грамматикой), если каждое ее правило имеет вид А- ы, где А ен%', 4ь~(Р()1«')*. Язык, порождаемый ОБ-грамматикой, удем называть ОБ-я з ы к о м. Те о р ем а 4.3. Для всякой ОБ-грал4А4атики Г можно построить Б-граш4атику Г такую, что 4. (Г') =4. (Г) — (Л). Д о к а з а т е л ь с т в о.
Добавив к основному словарю И ОБ-грамматики Г новый символ с и заменив каждое правило вида А — Л правилом А . с, получим Б-грамматику Г, такую, что Пр, Ь(Г,) = В(Г). Остается воспользоваться леммой 4.!О. (Полезно сравнить эту теорему с результатом упражнения 3.18.) Из теоремы 4,3 вместе с леммой 4.2 получаем !26 Е.ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ 1ГЛ.
4 С ле дет в не. Для есякой ОБ-грамматики Г можно построить эквивалентную ей ОБ-грамматику Г' такую, что правые части ее правил не содержат начального сим- вола и всякое ее правило, левая часть которого отлич- на от начального символа, имеет непустую правую часть. Теорема 4.4. Гомомарфный образ любого ОБ-язы- ка есть ОБ-язык. При этом для любой ОБ-грамматики с основным словарем (аь ..., а„) и любых п цепочек уь ..., у, в произвольном словаре с можно постраить ОБ-грамматику, порождающую язык ~р((. (!') ), где ~Р— гомоморфное отображение, определяемое условием Я7, 1, Доказательство. Пусть Г=((а, ..., а„), , )с). Без ограничения общности можно считать, что ь ..., а„, ((аь ..., а„) 0 йр) П Я=И. Положим Г'=(г., Ф' Щаь ...
..., а„), (, 11 () (а1- уь ..., а — у„)). Г' есть ОБ-грам- матика, и с,(Г') = $(с,(Г)). Полезно заметить, что понятие дерева вывода(можно ОБ-г ам естественным образом распространить на на случай ев -грамматики. Именно, рассмотрим произвольное р о вывода цепочки у из символа В в грамматике Г„, де- использованн~ой в доказательстве теоремы 4.3, ы ., и устра- В ним из него все висячие узлы, помеченные спмв символом с.
сякое полученное так Р,-дерево будет, по определению, деревом вывода цепочки Пргу из В в Г (У" — основной словарь Г). Можно было бы определить дерево вывода и прямо по выводу в ОБ-грамматике (н даже в ОНС- грамматике — см. упражнение 3.18), непосредственно обобщив определение из 5 3.1; это предоставляется чи- тателю. Висячие узлы с нетерминальными *) метками бу- дут тогда соответствовать точкам применения правил вида А-+.Л (для произвольных ОНС-грамматик — правил вида $Ац - БТ1).
Очевидным образом распространяется на ОБ-грам- матики и понятие однозначности (см. стр. 83). й 4.3. Необходимые условия бесконтекстности Когда нужно доказать, что тот или иной язык не яв- ляется бесконтекстным, часто оказывается полезной сле- дующая ) См. сааску "1 яа стр. 27. 4 4.п неОБКОдимые услОВия БесконтекстнОсти 1эт Теорем а 4.5. Для любого бесконечного Б-языка й найдутся такие натуральные числа г и э, эффективно определяемые по порождающей 1. Б-грамматике, что любая цепочка в ~ с,, длина которой болыие Г, может быть представлена е виде (1) в = х,у,гурхы где: (а) у,у, Ф Л; (б) ) у,еу,)~(з; (в) нри любом п=1, 2, ... цепочка в„= х,у",гу"х принадлежит А'.. Доказательство.
Покажем сначала, что если Г=(у', йу,!,В) — Б-грамматика без правил вида А- В, А, Вен йУ, то для любой цепочки ве=Ь(Г) такой, что ни одно ее дерево вывода не может быть простым, имеется представление вида (1), удовлетворяющее условиям (а) и (в), а также условию: (б') для некоторого символа А еи йу существует (А,у,гуз)-дерево, высота которого не превосходит р(РУ)+ 1. Действительно, пусть в — цепочка, обладающая указанным свойством, Т— какое-либо ее дерево вывода и С вЂ” индуцируемая этим деревом система составляющих для в. В дереве Т найдутся два различных узла а и 8, помеченных одним и тем же вспомогательным символом А и таких, что из а в 8 идет путь. Обозначим составляющие системы С, происходящие от узлов а и 8,— точнее, отвечающие им подцепочки в — через и и г соответственно.
Для подходящих цепочек хь хь уь уэ имеем, очевидно, и = у,гуэ, в = х,ихг = х1у,гузхк. Если У' н У" — соответственно полные а- и 8-поддеревья Т, то У' есть (А, и)-дерево и Ум есть (А, г) -дерево. Положим У~ — — У', Уэ = = БНЬ(УН У", У'), Уз= БНЬ(Уъ У",У') и т. д. Для каждого и=1, 2, ... У„является, очевидно, (А, у",гу"). деревом. Поэтому дерево Т„ = БНЬ(Т, У', У„) есть (1, х,у",гу"х )-дерево, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
