XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 97
Текст из файла (страница 97)
Заметим, что если КС-грамматика задана в приведенной форме и правые части правил не содержат вхождений аксиомы, то единственное допустимое правило с пустой правой частью (левой частью его является аксиома), если оно существует, используется только для порождения пустой цепочки. Исходнал грамматика из примера 8.10 этим свойством не обладает, так 616 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ как правило о'-+ А используется всякий раз при выводе слова четной длины. Кроме того, КС-грамматика, заданная в приведенной форме и не содержащая вхождений аксиомы в правых частях прв вил вывода, обладает еще одним интересным свойством: дерево вывода любой непустой цепочки является А-свободным. Таким образом, без ограничения общности можно считать деревья выводов непустых цепочек в 'КС-грзмматиках А-свободными. 8.3.
Лемма о разрастании длн КС-языков Для КС-языков выполняется „лемма о разрастании", аналогичнвл лемме о разрастании для регулярных языков (см. 7.8). Она формулирует необходимое условие того, что язык является контекстно-свободным. Теорема 8.4 (лемма о разрастании для КС-языков). Для любого КС-языка Ь существует натуральная константа й (зависящвя от Ь), такая, что любая цепочка г Е Ь, длина которой ф ) й, представима в виде соединения пяти цепочек г = ихыуо, где ~ху~ ) О, ~хну~ < й, и каждая цепочка г„= = их"юупи, и ) О, принадлежит Ь. ~ Так как Ь вЂ” КС-язык, то существует КС-граммап1ика С = = (у, Ф, я, Р), порождающая язык Ь, т.е.
Ь =ЦС). Фиксируем произвольно не1пврминал А е Ф и рассмотрим множество 2У(А) всех выводов, начинающихся с А, таких, что высотиа дерева вывода не превьппает числа ~Я~+ 1 нетерминалов грамматики О, увеличенного на единицу. Множество Р(А) конечно, так квк высота дерева вывода, а следовательно, и его длина ограничены сверху (см.
замечание 8.2). Таким образом, каждое множество Р(А) при А Е Ф есть конечное множество конечных выводов. Множество выводов Р определим как объединение множестве 2У(А) по всем А е Ф. Ясно, что и зто множество выводов конечно, твк как конечно множество нетерминвлов грамматики.
Введем подмножество А всех таких 8.3. Паина о рлэраставаи длл КС-лаыаов 617 цепочек в объединенном алфавите, что они являются последними цепочками выводов из Р. Иначе говоря, А — зто множество всех таких цепочек а в объединенном алфавите, что существует дерево вывода а (из некоторого нетерминала грамматики С), высота которого не больше ~И~+ 1. В силу конечности множества З конечно и множество А. Тогда положим й = п1ах~а), аеА т.е. введем константу й как наибольшую длину среди всех цепочек множества А.
Пусть теперь я Е Ь, причем ф > й. Тогда Я 1-о г, и в силу определения константы Й любое дерево вывода цепочки я имеет высоту, большую ~Ж~ + 1. Фиксируем какое-нибудь дерево Т вывода цепочки ю Выдеяим в дереве Т максимальное поддерево с корнем В, высота которого равна ~Я~+ 1 (рис. 8.25). г= и, иь л ю у оз о, Рис. 6.25 Тогда, согласно следствию 8.1, получим (для некоторых терминальных цепочек и1 и е1) 618 8.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЭЫКИ где г = и1я1ем т.е. существует вывод цепочки «1 = изхюуез, являющейся подцепочкой цепочки я, из нетерминала В, такой, что высота дерева этого вывода равна ~И~+ 1. Напомним, что высота дерева есть максимальная длика пуши в этом дереве ю корня в лист. Так как длина пути в дереве вывода КС-грамматики равна числу замен нетерминалов в некотором фрагменте вывода (см.
8.1), то при выводе цепочки я1 из В число замен нетерминалов строго больше числа всех нетерминалов грамматики С. Это означает, что в выводе «1 из В какой-то нетерминал Я повторяется дважды (возможно, что Я = В) и на некотором пути ю вершины В в один из листьев будут по крайней мере две разные вершины, помеченные одним и тем же нетерминаяом Я. Тогда рассмотрим два максимальных поддерева дерева Т, корневые вершины которых являютсл указанными вьппе вершинами с меткой Я (см. рис.
8.25). Выделению этих максимальных поддеревьев соответствует выделение фрагментов вывода я1 из В, таких, что для некоторых терминальных цепочек из, ез, х, у, ш выполняется выводимость В 1" изчез 1- изхЯуез 1 * изхюуез, (8.2) где я~ — — изхшуег.
Соотношения (8.2) показывают, что имеют место выводи- мости Ц~-'ХЯу (8.3) (8.4) Это значит, что существует дерево вьшода цепочки хшу из нетерминала Я („большое" дерево с корневой вершиной Я на рис. 8.25) и в нем — максимальное поддерево с корневой вершиной, помеченной тем же символом Я, являющееся деревом вывода цепочки и из Я („маленькое" дерево с корневой вершиной Я на рис. 8.25). При этом, так как „большое" дерево с о.З. Лемма о разрастании яви КС-вэыков 619 корневой вершиной Я является поддеревом дерева с корневой вершиной В высотой ~Ф~ + 1, то его высота будет не больше чем «М~ + 1, откуда в силу выбора константы й имеем )хшу~ ( й. Объединяя (8.1) и (8.2), получим такое представление вывода цепочки х из аксиомы Я: Я «-" и1Ве1 ~' и1игЯеге1 «-' и1игхЯуеге1 «-' и1игхшуеге«.
(8.5) Полагая и = и1иг и е = еге«, получим х = ихшуе> и тем самым мы доказали представление цепочки х в виде соединения определенных пяти цепочек. Из (8.5) следует, что, получив (при выводе х из Я) цепочку и~игЯегем можно с учетом (8.4) сразу из нетерминала Я вывести цепочку ш,и тогда Я ~* и«Ве««-' и«игЯеге1 «-» и«игшеге1 = ишу (8.6) (в выводе (8.5) выбрасываем последовательность шагов над фигурной скобкой). В то же время вывод (8.5) можно с учетом (8.3) модифицировать так, что после получения цепочки и1игФ~ге1 = иФ многократно (не менее одного раза) повторять вывод цепочки хну из ф Я «-* и«Ве1 «-» и«игЯеге1 = = иЯе «-" ихЯре «-' иххЯуре «-' ...
«-' «-» иха«~рве «-» ихашрае (8 7) (в выводе (8.5) последовательность шагов над фигурной скобкой повторяем и раз). Итак, в силу (8.6) цепочка ге = ише Е Ь, а в силу (8.7) и цепочка х„= их"шрае для любого и > 0 принадлежит языку Ь. Тем самым мы доказали, что (Чи > 0)(их"шр"е Е Ь). 620 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Осталось доказать, что длина цепочки ху не меньше 1 (или, что равносильно, цепочки х и у не являются одновременно пустыми). Согласно теореме 8.2, можно считать без ограничения общности, что в множестве правил вывода грамматики С нет ни Л-правил (кроме, быть может, правила э -~ Л), ни цепных правил.
Кроме того, в силу замечания 8.6 можно считать, что правило э'-> Л применяется только при выводе пустой цепочки, а поскольку высота дерева цепочки» строго больше 1, то » ф Л и правило э' -+ Л не применяется при выводе» из аксиомы э'. Тогда, предполагал, что х = у = Л, получим Я 1-" Я, а это возможно лишь при условии применения в соответствующем выводе цепных правил или правил с пустой правой частью, что ввиду сказанного выше не может иметь места. Итак, цепочка ху не пуста, т.е. )ху~ > О, что и завершает доказательство теоремы. ~ Следствие 8.2. В любом бесконечном КС-языке существует последовательность слов, длины которых образуют возрастаюшую арифметическую прогрессию.
~ Пусть КС-язык Ь бесконечен. Тогда в нем нет цепочки наибольшей длины. Следовательно, найдется цепочка» Е Ь, длина которой больше константы к, определяемой леммой о разрастании. Согласно этой лемме, цепочка» может быть представлена в виде» = ихыуи для некоторых цепочек и, х, и, у, е, таких, что ~хшу~ ( (й, ~ху~ > О. Тогда последовательность (»„= = их"тюу"и)„>е является искомой, так как длины ее цепочек образуют возрастающую арифметическую прогрессию со знаменателем ~ху!.
М Замечание 8.7. Любой конечный язык (пм..., и„Д (в каком-то алфавите У) порождается КС-грамматикой с множеством правил Я -+ п1~... ~и,в. Дерево вывода любой цепочки в этой грамматике имеет высоту, не большую 1 (высоту 0 име- е.З. Лемма о разрастании дяя КС-языков 621 ет дерево вывода нулевой длины аксиомы о из себя самой, а каждая терминальная цепочка,т.е. цепочка и;, з = 1,пз, имеет дерево вывода высоты 1).
Следовательно, в данном случае константа й равна наибольшей длине цепочки ем и цепочки, длина которой была бы больше Й, не существует. Таким образом, для конечного языка утверждение леммы о разрастании тривиально выполняется, а именно, не существует цепочек, длины которых превосходят константу Й. Пример 8.11. а.
Язык (а": п > 01 не является контекстно-свободным, поскольку из длин принадлежащих ему слов нельзя образовать арифметическую прогрессию: 1п+1)~-и' = = 2п+1. б. Язык (а'. я — простое число) не является КС-юыком по той же причине. в. Рассмотрим юык (анЬосн )и > 0). Длины его слов образуют арифметическую прогрессию, но тем не менее этот язык не является контекстно-свободным. Действительно, предположим противное. Тогда для любого достаточно большого и слово а"Ь"с" можно представить в виде ихюуе.
Проанализируем, как могут располагаться в;слове цепочки х, ш и р. Поскольку условие леммы о разрастании должно выполняться для всех достаточно длинных слов языка, т.е. слов, длина которых строго больше константы й из леммы, то в целях проверки невыполнения условия можно брать слова; длина которых заведомо превьппает указанную константу'. Для анвлюируемого в этой задаче языка примем, что и > й.
Тогда возможны следующие случаи: 'Предполагая, что язык является контекстно-свободным, мы тем самым в силу леммы о разрастании предполагаем, что оказывается фиксированной какая-то константа й, о которой идет речь в условии леммы. Мы не можем знать значения этой константы, но это нам и ве нужно: достаточно знать, что вследствие ныпего предположения константа Й как-то фвксирована, и мы можем быть уверены в том, что в бесконечном КС-языке найдутся цепочки, двины которых превысят я.
622 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ 1) хаву = а~, где 1 < Ь < п, а а обозначает одну из букв а, 6, с (т.е. цепочка х1юу целиком расположена или в „зоне" символов а, или в „зоне" символов 6, или в „зоне" символов с); 2) хну = а'Ь"' или хищ = 6~с"', где 1+ т < й < п и 1, га > 0 (т.е. цепочка хюу расположена „на стыках зон" различных символов и содержит ненулевое число символов каждой из „зон").
В силу выбора числа п никакие другие способы расположения подцепочки хюу в цепочке а" Ь" с" невозможны (отсюда следует, что подходящий выбор числа и позволил нам уменьшить число вариантов расположения подцепочки хюу в цепочке языка). Теперь если мы станем повторять („накачивать") цепочки х и у в первом случае, то начнет расти число одного из символов а, Ь или с, тогда как число остальных двух символов будет оставаться прежним, и получаемые при этом цепочки уже не будут принадлежать заданному языку. Во втором же случае при „накачке" возникнут цепочки, содержащие вхождение цепочки Ьб илн сЬ, что также недопустимо (символы а, Ь, с начнут „перемешиваться").
Получается, что мы не можем представить любую достаточно длинную цепочку а"Ьас" в виде ихтюую так, чтобы при этом выполнялось условие леммы о разрастании. Следовательно, исходный язык не является контекстно-свободным. В целом техника доказательства с помощью леммы о разрастании для КС-языков „отрицательных" утверждений типа „данный язык не является контекстно-свободным" аналогична технике доказательства утверждений о нерегулярности языков с использованием леммы о разрастании для регулярных языков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
