XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 93
Текст из файла (страница 93)
8.1. Корень этого дерева (кусуаа) помечен заменяемым на данном шаге нетерминалом, а метки лисшьев, перечисленные слева направо, образуют цепочку, полученную после применения правила (1) на первом шаге. Вообще же цепочку, полученную в результате такого перечисления меток листьев, называют есроной дерева'. А На втором шаге применяется правило (2) и производится замена вхохсдеиил (единственного в данном случае) символа А цепочкой ВВ.
Поэтому вер- В В шину дерева на рис. 8.1 с меткой А заменим кустом, рис. а.й как показано на рис. 8.2. Допускал некоторую вольность речи, кроной дерева называют и соответствующую пересюаноеку инозсесюеа листьев. 8А. КС-грамматиии. Деревьв амиода. Одиоаиатиость 589 После двух шагов получим дерево, изображенное на рис. 8.3. Действуя аналогично, после третьего шага получим дерево, показанное на рис. 8А. Л'Л В В А А Рис. 8.4 В В Рис.
8.3 Четвертый шаг требует более подробного комментария. Здесь в кроне дерева имеется несколько вхождений символа А. На четвертом шаге первое вхоэедеиие 8 символа А в цепочку ВВАА заменяется пустой цепочкой. Поэтому очередной шаг в построении дерева будет состоять А В С в том, что первый лист с меткой А в кроне дерева должен быть заменен кустом с корнем А и единственным листом с меткой Л. Тогда получим дерево, изображенное на рис.
8.5. Крона вновь полученного дерева— это цепочка ВВВЛА, выведенная из аксиомы за четыре шага. Онв„как элемент свободного,иоиоида (т' 0 Ж)', равна (в силу известных свойств пустой цепочки — см. 7.1) цепочке ВВВА. Обратим здесь внимание на то, что, хотя пустая цепочка и не является символом ни одного из алфавитов грамматики, она, как было уже сказано, может быть меткой вершины дерева вывода. Тем самым в дереве вывода фиксируются все вхождения выбрасываемых, т.е. заменяемых в процессе вывода пустой цепочкой, нетерминалов. Это равносильно выделению в выводимой цепочке некоторых вхождений в нее пустой цепочки.
На пятом шаге первое вхождение символа В в цепочку ВВВА заменяется цепочкой СС. Этому отвечает новое по- 590 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ С С Рис. 8.6 Л1Л л1 1л С С А Ь Ь а с Рис. 8.Т Рис. а.а Из разобранного примера следует, что шаги построения дерева вывода в точности соответствуют шагам самого вывода, причем после каждого шага получаем некоторое дерево (назовем его часпъичным деревом вывода, полученным после данного шага). Начинаем построение с корня, и его меткой служит тот нетерминал, с которого начинается вывод (в частности, это может быть аксиома грамматики). Если на очередном шаге вывода применяется правило В -+ Х1 Хз...
Х~ > где Х; (1 < с ( ш) — либо символ объединенного алфавита, либо пустая цепочка, то тот лист частичного дерева вывода, полученного перед этим шагом, который имеет метку В и соответствует заменяемому вхождению символа В, заменяется кустом с корнем В и листьями Х1, Хз1 ", Хм Замечание 8.1.
1. Прежде всего нужно отчетливо понимать, что на каждом шаге построения дерева вывода „развер- строение на очередном дереве, состоящее в замене первого листа кроны с меткой В кустом, изображенным на рис. 8.6, после чего получим дерево, показанное на рис. 8.7. Действуя дальше точно так же, получим в результате дерево вывода, изображенное на рис.
8.8. 8.1. КС-грамматики. Деревьв нывода. Однозначность 591 тываетсял в куст не любая вершина, меткой которой служит некий нетерминал, а именно та вершина, которан соответствует заменяемому вхождению указанного нетерминала. 2. Совершенно необязательно рассматривать А только деревья выводов терминальных цепочек из аксиомы. Дерево вывода может быть построено по выводу любой цепочки в объединенном В н алфавите из любого нетерминала грамматики.,г ~ Так, мы могли бы на базе разобранного вьппе С С а примера нарисовать дерево вывода цепочки ССа Рис.
В.в ю нетерминала А, показанное на рис. 8.9. 3. Можно заметить, что разные выводы одной и той же цепочки из заданного нетерминала могут дать одно и то же дерево вывода. Так, дерево, изображенное на рис. 8.9, можно построить по двум различным выводам: А 1- ВВ )- ССВ ~ ССа А 1- ВВ ~- Ва ~- ССа. Выводы, имеющие одно и то же дерево вывода, естественно считать эквивалентными. Они различаются между собой только порядком, в котором применяются правила вывода'. Дерево вывода и служит способом наглядного юображения всех эквивалентных выводов.
Кроме того, как мы увидим позже, дерево вывода является одним из основных инструментов доказательства утверждений о КС-языках и КС-грамматиках. Теперь дадим формальное определение дерева вывода. Рассмотрим множество (ориентированных) деревьев, вершины которых помечены символами некоторого алфавита $У. Ориентированное дерево, каждая вершина которого помечена символом некоторого алфавита, будем называть полеечемкььм деревом.
*Здесь, в рамках сугубо неформального изложения, мы не даем строгого определении зквивалевтных выводов. 592 В. КОНТЕКСХНО-СВОБОДНЫЕ ЯЗЫКИ Если, кроме того, задано определенное правило перечисления меток вершин дерева, образующих некоторое подмножество вершин всего дерева, в частности листьев дерева,то такое помеченное дерево называют упорядоченным деревом.
Всюду в дальнейшем, изображая деревья выводов, условимся понимать их как упорядоченные деревья, метки листьев которых перечисляются всегда слева направо. Слева направо будем также перечислять и сыновеб каждой вершимы. Будем считать, что в машинном представлении деревьев выводов порядок „слева направо" при изображении дерева на плоскости соответствует порядку от первого элемента списка смеэсносши вершины к последнему.
Дерево, корень которого помечен символом А, а листья имеют метки Хм Хз, ..., Х, договоримся записывать в виде цепочки А Д Х1 Хз... Х,„ (с двумя стрелками). Если рассматриваемое дерево является кустом, то условимся писать А (, Х1 Хз... Хв, (с одной стрелкой). Листья дерева„обозначенного таким образом, отождествим с символами цепочки Хм Хз, ..., Х,„. Это значит, что, говоря о листе Х;, мы имеем в виду лист помеченного дерева, меткой которого является символ Х; и который в перечислении листьев слева направо получает номер 1.
Тем самым устанавливается взаимно однозначное соответствие между листьями помеченного дерева и вхождениями символов алфавита Ю в цепочку Хм Хз, ..., Хв,. Например, записывая дерево в виде А Ц. ВВСВС, мы можем говорить о листе В, соответствующем первому вхождению символа В в цепочку ВВСВС, или же, обозначив ВВСВС через а, о листе а(1). Тогда листья а(1), а(2) и а(4) — это разные листья дерева, хотя их меткой является один и тот же символ алфавита Ю. 8.1. КС-граымаеиви.
Деревьв вывода. Одвоаиачиоетъ 593 1 1 1 1 Рис. 8.10 Я ~- АВС ~- ВВВС 1-аВВС ~- аССВС1 аААСВС ~- ~- аЛАСВС 1- аЛЛСВС )- аЛЛААВС ~- аЛЛЛАВС ~- ~- аЛЛЛЛВС ~- аЛЛЛЛаС ~- аЛЛЛЛаЬ = ааЬ 8.10. В этом дереве любой Л ЛР 1~ ~ а а А А Ь 1 В В а а Рис. 8.11 Расширим множество помеченных дере. вьев, допуская в качестве меток их вершин и пустую цепочку. В этом случае, в записи А Д Х~Х1...Хо,, представляющей дерево с корнем А и листьями Х1, Хг, ..., Х,в, среди меток листьев, т.е. элементов Х;, 1 = 1,т, могут быть и пустые цепочки. Тогда, говоря о листе с меткой Л, нужно указывать, какое вхождение пустой цепочки Л в цепочку Х~Х1...
Х~ имеется в виду. Пример 8.2. а. Дерево вывода, изображенное на рис. 8.8, может быть обозначено так: ЯД ЬЬааЛаа. В нем лист с меткой Л соответствует вхождению (ЬЬаа, Л, аа) пустой цепочки в цепочку ЬЬаааа. б. Для грамматики из примера 8.1 вывод имеет дерево, показанное на рис. его лист с меткой Л соответствует одному и тому же вхождению пустой цепочки в выводимую цепочку ааЬ, а именно вхождению (а, Л, аЬ), твк квк для любого натурального и выполняется равенство Л" =Л. в. Представленное на рис. 8.11 дерево вывода цепочки ааЬаа может быть задано записью 544.ааЛЛЬЛаа.
Оно имеет три листа с меткой Л. Л~! ~Л Л Л 1~~~ 594 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Первые два соответствуют вхождению (аа, Л, Ьаа), а третье — вхождению (ааЬ, Л, аа) пустой цепочки в выводимую цепочку. Помеченное дерево А Д Х1 Хз... Х называют Л-свободкым, если среди меток Хм Хз, ..., Хтв его листьев нет пустой цепочки. Из предыдущих примеров можно заключить, что не всякая цепочка, вьпюдимзя в КС-грамматике из какого-либо нетерминала, имеет Л-свободное дерево вывода. Помеченное дерево, полученное из дерева АДХт ...Х; 1ХтХт+т...Х, заменой листа Х; ф Л деревом Х; ).).
У1... Уь, будем записывать в виде цепочки А ).),Х1...Х; 1[Хт.) ). У1 ...Уь]Хт+1 ...Х,в. Это дерево, поскольку в нем вместо листа Х;, возникают листья с метками Ум..., Ую можно представить также в виде А).).Х1 ...Хт 1У1...УьХт+1...Х~в. Дерево вывода т4епочки р" в объединенном алфавите из нетерминала А в ХС-эрамматпике ст = (У, Ж, о, Р)— это помеченное дерево, метками вершин которого являются символы объединенного алфавита У ОФ или пустая цепочка Л и которое строится по следующим правилам: 1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом А (в данном случае цепочка б = А); 2) дерево вывода А 1- Л вЂ” это дерево А ~, Л (в данном случае цепочка р = Л); 3) дерево вывода А 1- ст, где ст — непустая цепочка, есть дерево А ) ст; 4) если ст — цепочка в объединенном алфавите и АДХтХз...Х~в дерево некоторого вывода 1.1 этой цепочки из нетерминзла А, где а=ХтХз...Х,в и для каждого 1=1,тп Х; Е УОФО(Л1, а 8.1. КО-грамматики.
Деревьв вывода. Одиоаиачиооть 595 для некоторого 6 (1 < ь' < ча) Х; = В е М вЂ” нетерминальный символ грамматики С, и в множестве правил вывода Р грамматики С есть правило В -~ У1... уа, то дерево АДХ~...Х; 1~Х; 61'~...Уа]Ъ;+1...Ув есть дерево такого вывода цепочки из нетерминэла А, что его последний шаг имеет вид Х~...Х; 1ВХ;+1...Х~ ~- ~-в~ам.хь Х1" Х-М" ~ьХ~+1 "Х 1, а вывод цепочки а=Х1...Х; 1ВХьь1...Х,„из А совпадает с ав.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
