XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 96
Текст из файла (страница 96)
608 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Можно доказать, что описанный алгоритм удаления цепных правил дает грамматику, зквивалентную исходной. Замечание 8.4. К цепным правилам относится и правило А -д А. Если такое правило находится в множестве правил грамматики или появляется при удалении Л-правил (см. пример 8.4), то оно должно быть просто удалено из множества правил. ф Обратимся к примеру, из которого станет ясно, что удаление Л-цравил может привести к появлению в множестве правил заданной КС-грамматики цепных правил.
Пример 8.6. Рассмотрим грамматику Св из примера 8.1. Для удобства перепишем ее определение: Со=((а,Ь), (В,А,В,С) В, Ре), где множество правил вывода Ре имеет вид В ~ АВС, (1) А -+ ВВ, (2) А -+ Л, (3) В -~ СС, (4) В -д а, (5) С ~АА, (6) С -+ Ь. (7) Удаляем Л-правила. Множество Мо = (А) (правило (3)). Далее, Фд = (А, С), поскольку в правиле (6) правая часть есть непустая цепочка нетерминалов из Жо; Фз = (А, С, В) (правило (4)), Фз = (А, С, В, Я). Так как Жз совпало с множеством всех нетерминалов грамматики, то Мз = М,. Согласно описанному вьппе алгоритму удаления Л-правил, получим следующую грамматику: Я вЂ” д АВС~АВ~АС)ВС)А~В)С)Л, А-+ВВ~В, В ~ СС~ С~а, С-+ АА~А)Ь. 8.2. Приаедеииаа форма КС-грамматики 609 Мы видим, что в результате удаления Л-правил получилось много цепных правил (которых не было в исходной грамматике).
Применение алгоритма удаления цепных правил даст следующие множества №~. уе уе И~ =(Я,С), Д~в =ФА) 2Чсе = (Я, А), Жл = (Я, С, В, А); Фвэ = (Я А С В)' Д~л=СЯ,А,В,С). Таким образом, №~ — — №в — — №с — — (Я, А, В, С) (множество всех нетерминалов грамматики). Новое множество правил, не содержащее цепных правил, будет иметь следующий вид: Я -~ АВС ~ АВ ~ АС ~ ВС ~ Л ~ ВВ ) СС ~ АА ~ а ) Ь; А -~ ВВ~СС~АА~а~Ь; В-+ СС~ВВ~АА~а~Ь; С-+АА~ВВ~СС~а~Ь. м нво1 Замечание 8.5. Теорема 8.2 позволяет утверждать, что любую КС-грамматику можно преобразовать к эквивалентной КС-грамматике, множество правил вывода которой содержит только КЗ-правила, т.е.
правила вида сеА~З-+ а"у,8 при а =,8 = Л и у ~ Л. Единственным исключением может быть правило Я -+ Л для аксиомы Я. Можно показать, что добавление к множеству правил КЗ-граммаепмии правила, предусматривающего замену аксиомы пустой цепочкой, не приводит к существенному изменению класса языков, порождаемых КЗ-грамматиками.
Единственное отличие языка, порождаемого такой грамматикой, от КЗ-лэмма состоит в том, что он может содержать пустую цепочку, тогда как ни один КЗ-язык, будучи иеукорачивающим лэьпсоае, пустой цепочки не содержит. 610 8. КОНТЕКСТНО- СВОБОДНЫЕ ЯЗЫКИ Следовательно, если в множестве правил КЗ-грамматики разрешить кроме КЗ-правил также и правило В -> Л (где В— аксиома грамматики), то любую КС-грамматику можно преобразовать к эквивалентной КС-грамматике, являющейся частным случаем КЗ-грамматики (с правилом о' -+ Д). Определение 8.3.
Нетерминальный символ А КС-грамматики С = (К Ф, о', Р) называют бесполезным, если из него не выводится ни одна терминальная цепочка, т.е. не существует такого х Е У', что А~-пх. Бесполезный нетерминая КС-грамматики может быть удален (вместе со всеми правилами, в которые он входит) без изменения языка, порождаемого данной грамматикой. Следующая теорема утверждает существование алгоритма удаления бесполезных нетерминальных символов.
Теорема 8.3. Для каждой КС-грамматики С = (У, М, В, Р) может быть построена эквивалентная ей КС-грамматика, не содержащая бесполезных нетерминальных символов. ~ Алгоритм удаления бесполезных нетерминзлов состоит в ре. куррентном вычислении множества Ф„С М всех нетерминалов грамматики С, иэ которых выводится какая-либо терминальная цепочка.
Сначала вычисляем множество Фо всех нетерминаюв, из которых терминальная цепочка выводится за один шаг. Для этого просматриваем множество правил Р, отмечая в нем все правила вида А — ~ х, где х Е $'". Другими сювами, Фе = (А: в Р есть правило А -+ х, х Е У'~. Затем вычисляем множество Ф1, добавляя к Ме множество всех таких нетерминаюв В, что существует правило вывода в Р вида В -+,9, где,9 — цепочка, содержащая как терминалы, так и нетерминалы из множества Ме.
Таким образом, в Ф1 попадут все нетерминалы В, такие, что существует вывод 611 8.2. Приаедеииак форма КО-грамматики а В х х, В1 х~ Рмс. 8.21 терминальной цепочки из В, и высота дерева зтого вывода не больше 2 (рис. 8.21). В общем случае для множества Ж; (1 > 1) получаем формулу Ф, = Ф; ~ 0 1А: в Р есть правило А -+ а, где а Е (Ф; 1 0 У)'). Это множество содержит все такие нетерминалы В, что высота дерева вывода любой терминальной цепочки из В не превышает т'+ 1.
Для наименьшего у, такого, что Ж~ — — Ф~» 1, полагаем № = = М~. Из построения множества № следует, что зто множество всех таких нетерминалов А грамматики С, что существует вывод (ненулевой длины) А 1-+ х для некоторого х е У", что и требовалось доказать. Тогда все нетерминалы из Ж '1 № бесполезны. ° В частности, если Я ф №, то Ь(6) = И, и наоборот. Таким образом решаетса проблема пустпотпы дав КС-ерамааапапп, которая формулируется следующим образом: для данной КС-грамматики выяснить, пуст ли язык, ею порождаемый. Из предыдущих рассмотрений ясно, что для ответа на этот вопрос достаточно вычислить множество бесполезных нетерминалов грамматики и проверить, находится ли среди них аксиома грамматики.
Язык, порождаемый КС-грамматикой, пуст тогда и только тогда, когда ее аксиома бесполезна. 10* 612 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Пример 8.7. Пусть множество Р правил вывода КС-грамматики С= ((а, Ь), (Я,А,В,С), В, Р) имеет вид В-+аА)ЬВ, А -+ ЬАа, В-+аВ~ЬВ~а~Ь, С -+ ВаА. Применяя алгоритм из доказательства теоремы 8.3, получаем Фо = (В), так как в Р имеются только два правила, правые части которых — терминальные цепочки В -+ а и В -~ Ь. С целью вычисления множества Ф1 найдем те правила, правые части которых кроме терминалов содержат только нетерминальный символ В: это будут правила Я-~ ЬВ и В ~ аВ, т.е. Ф~ = (В, В). Так как есть только одно правило, правая часть которого со-, держит вхождение символа В, а именно правило В -+ ЬВ, то Жэ = Ф1 = Ж„= (В,В).
Символы А и С бесполезны. Все правила, содержащие вхождения этих символов, можно удалить. В итоге получим грамматику с таким множеством правил: Я~ЬВ, В -+ аВ ~ЬВ~а~6. Определение 8.4. Символ Х объединенного алфавита У О У КС-грамматики С = (Ъ; Ж, Я, Р) называют медосшплсемым, если из аксиомы грамматики не выводится ни одна цепочка, содержащая вхождение символа Х, т.е. не существует таких цепочек а, ~3 е (У 0 Ф)', что В 1-с аХ,О. Из самого понятия недостижимого символа ясно, что такие символы можно удалить из грамматики (удалив все правила, которые их содержат) без изменения порождаемого ею языка. Займемся разработкой алгоритма удаления недостижимых символов.
Введем в рассмотрение понятие графа КС-грамматики. е.2. Приведегвее форма КС-грвммвтвли 613 Определение 8.5. Назовем граЯом КС-граммапьини С = (У, Ф, Я, Р) ориенелированныб граф, множество вершин которого равно У 0 Ж 0 (А), а множество дуг определяется следующим образом. Дуга из вершины с меткой А ведет в вершину В тогда и только тогда, когда правило А -+ сеВ8 (а, ~3 Е (У 0 Ж)') принадлежит множеству Р правил вывода грамматики С. Понятие графа КС-грамматики ни в коем случае нельзя путать с понятием дерева вывода в КС-грамматике, так как дерево вывода строится по конкретному выводу, а граф КС-грамматики строится по множеству правил вывода и характеризует саму грамматику в целом.
Пример 8.8. Граф грамматики иэ примера 8.7 представлен на рис. 8.22. Опираясь на определение 8А, можно показать, что символ Х КС-грамматики С = (У, Ф, Я, Р) достижим тогда и толь- 8 А а ко тогда, когда в графе грамматики существует путь из вершины Я грамматики С в вершину Х, и задача распоэнава- Ь ния достижимости символов в КС-грам- В матиках сводится тем самым к задаче распознавания достижимости в ориентированных графах иэ заданной вершины.
р Для ее решения достаточно воспользоваться, например, алгоритмом поиска в ширину (см. 5.5). В примере 8.8 (см. рис. 8.22) символ С не достижим. Удаление бесполезных нетерминалов может привести к появлению недостижимых символов. Пример 8.9.
Модифицируем грамматику из примера 8.7, добавив к множеству ее терминалов новый символ д и к множеству ее правил вывода правило А -~ СИ. 614 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Граф модифицированной грамматики приведен на рис. 8.23. Нетерминалы А и С бесполезны, хотя и достижимы. Удаляя их вместе со всеми правилами, в которые они входят, получим КС-грамматику, граф которой изображен на рис.
8.24. Терминал д стал недостижимым. Рис. 8.23 Рис. 8.24 Определение 6.6. КС-грамматика считается заданной в приведенной форме, если множество ее правил вывода не содержит А-правил и цепных правил, множество ее нетерминалов не содержит бесполезных нетермнналов, а объединенный алфавит не содержит недостижимых символов. Рассмотренные вьппе алгоритмы любую КС-грамматику позволяют преобразовать к эквивалентной КС-грамматике, заданной в приведенной форме.
Заметим, что поскольку удаление А-правил может привести к появлению цепных правил (см. пример 8.6), а удаление бесполезных нетерминалов — к появлению недостижимых символов, то построение приведенной формы КС-грамматики нужно проводить в такой последовательности: 1) удалить Л-правила, 2) удалить цепные правила, 3) удалить бесполезные нетерминалы, 4) удалить недостижимые символы. Замечание 6.6. К числу важных преобразований КС-грамматики относят также преобразование, состоящее в удалении аксиомы нз правых частей правил вывода.
Можно до- Л.2. Прваедеаааа форма КС-грамматика 615 казать, что любая КС-грамматика преобразуется к эквива лентной КС-грамматике, не содержащей вхождений аксиомы в правые части правил вывода. Действительно, для этого достаточно ввести новый нетерминал Я1 (отличный от всех нетерминэлов исходной грамматики), объявить его аксиомой и добавить правило Я1 -+ Я, после чего появившееся цепное правило и недопустимые Л-правила, которые могут при этом возникнуть, удаляются согласно приведенным вьппе алгоритмам.
Пример 8.10. Грамматика с множеством правил Я -+ аЯа ) ЬЯЬ | а ~ Ь | Л, порождающая множество всех палиндромов в алфавите 1а, Ь1 (см. пример 7.5.в), преобразуется после удаления аксиомы из правых частей правил вывода в грамматику с аксиомой Я1 и следующим множеством правил: Я1 -+ Я; Я~аЯа~ЬЯЬ|а~Ь|Л. Появились, как мы видим, цепное правило и, поскольку символ Я в новой грамматике уже не является аксиомой, Л-правило Я-> Л, которое следует удалить. Выполняя это, получим окончательно следующее множество правил: 81 -+аЯа)ЬЯЬ|аа)ЬЬ|а(Ь|Л, Я ~ аЯа)ЬБЬ|аа~ЬЬ~а~Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
