Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 58
Текст из файла (страница 58)
Применение описанного алгоритма к грамматике из примера 7.1, г дает грамматику 1-» 1 + Т ! 1 — Т ) Т ° М ( Т1М ( (1) ! а ( Ь | с; Т-«- Т «М ( ТIМ ~ (1)1а1Ь | с; М -» (1) / а ! Ь ! с. Сравнение этих двух грамматик показывает, что наличие цепных правил имеет как достоинства, так и недостатки. Главным недостатком является громоздкость вывода: построив дерево вывода в последней грамматике для выражения а Ь+ с, можно убедиться, что оно компактнее дерева для того же выражения в грамматике примера 7.1; г (см. рис. 7.1) за счет отсутствия ребер Т- М, М-~-Е и 1-«.Т. С другой стороны, грамматика примера 7.5 содержит 18 правил, тогда как в примере 7.1, г — 11 правил.
Цепные правила дают возможность своеобразного «вынесения за скобки» (и, наоборот, описанный выше алгоритм их устранения «раскрывает скобки», размножая правые части правил),чтоупрощает описание грамматики в целом. Поэтому такие правила используются при задании языков программирования, хотя они и усложняют вывод. Докажем теперь, что алгоритм устранения цепных правил в грамматике 6 дает эквивалентную грамматику 6'. Пусть Л» — — 1, аь ..., а — левосторонний вывод в 6 цепочки а, и ໠— самая левая цепочка, к которой применяется цепное правило.
Тогда в Л, имеются цепочки вида а»= =)1«А8м я«=11«СК аы«=8«уК причем на отрезке я»,...,я« применены цепные правила, а аьы получено из а~ правилом С-«-у. Рассмотрим теперь последовательность Л« — — 1, аь...,я», а««ь ..., а . В ней переход от я» к аьы осуществляется применением правила С-«у, которое по описанному алгоритму принадлежит Й'; кроме того, Л, содержит по крайней мере на одно цепное правило меньше, чем Л,. Повторяя эту процедуру, в конечном счете получаем последовательность 278 Ь 7, ..., а, которая не содержит цепных правил; в ней все переходы к следующей цепочке осуществляются либо неценными правилами 6, либо новыми правилами вида С-~-у, которые включены в 77' на втором этапе описанного алгоритма. Так как цепочка а при этом преобразовании сохранилась, то Л„является выводом а в 6', следовательно, 7 ('6)ы7,(6'). Обратное включение Ь(6')с:-1.('6) также доказывается преобразованием вывода.
Одним из явных достоинств грамматик без цепных правил является отсутствие циклов в выводах, т. е. выводимостей вида А=~"'А. Для неукорачивающих КС-грамматик это равносильно тому, что все выводы в них — бесповторные, ни одна цепочка в выводе не повторяется. В свою очередь, бесповторность вывода позволяет установить фундаментальное для КС-грамматик обстоятельство — линейную зависимость между длиной вывода и длиной выводимой цепочки. Теорема 7.3. Если 6= ( г', )г', Я, 7 ) — приведенная КС-грамматика без циклов, то существуют такие константы с, и см зависящие от 6, что для любого вывода Ь(а) цепочки иена.('6) сг)а) ~( ~Ь(а) ~~(с,(а(, где Ь(а) ! — длина вывода Л(а). усть Йс=(яг(,й, — максимальная длина правой части в правилах 6.
Так как 6 не содержит циклов и укорачивающих правил, то для любого вывода (З~ьо 7 17!) (р( и, следовательно, для вывода 7=ьь '"' 7(у()(а(. Поэтому (Л(а) ((йо!а(. С другой стороны, (а)(й,)Л(а) (. Отсюда (а(/Й1~ ((Л(а) (. Алгоритмические проблемы для грамматик. Поскольку класс множеств, порождаемых грамматиками, совпадает с классом перечислимых множеств (теорема 7.1), то для языков типа О справедлив аналог теоремы Райса: никакое нетривиальное свойство языков типа О ие является алгоритмически разрешимым; точнее, ни для какого нетривиального свойства языков типа О не существует алгоритма, который по произвольной грамматике 6 выяснял бы, обладает ли этим свойством язык Ь(6). Для языков типа 1 уже существуют разрешимые проблемы.
Например, для любой цепочки а и любого языка Ь типа ! разрешима проблема принадлежности а языку Ь (теорема 7.2). Однако проблемы пустоты н бесконечности языка, порождаемого данной грамматикой типа 1, неразрешимы. Для языков типа 2 эти 279 две проблемы разрешимы.
Разрешимость проблемы пустоты непосредственно следует из наличия алгоритмов приведения КС-грамматик, а именно: язык Ь(6) непуст, если и только если начальный символ 6 — производящий. Разрешимость проблемы бесконечности следует из более сильного утверждения о характере бесконечности КС-языков, называемого иногда клеммой о разрастании». Теорема 7А. Для любой КС-грамматики 6= (У, Л, 7 ) существуют такие числа р и д, что каждая цепочка яен7.('6) длины, большей р, представима в виде а буыбе, где у непусто либо б непусто, ~увб~(д, причем все цепочки вида 117"вб"е также принадлежат Л('6).
Построим приведенную грамматику 6', эквивалентную 6 и не содержащую цепных правил. Пусть й — число нетерминальных символов в 6'. Существует лишь конечное число цепочек в Ь(6'), высота вывода которых не превышает й. Обозначим через р максимум длин таких цепочек. Если ~а) ) р, то дерево вывода и имеет высоту )Й, т. е. содержит путь от корня к концевой вершине длины )й. Рассмотрим конец этого пути длиной й+1. Последовательности его вершин соответствует последовательность из Й+1 нетерминальных символов А;„...,А; ч,, в которой хотя бы один символ должен повториться: А;, =Ад — — В, г(за-й+ +1.
Поддереву с вершиной А;,=В соответствует вывод в 6' вида В=»-*рВп=~.'увб, где умбенУ*, причем у непусто либо б непусто; это следует из того, что 6' — приведенная и не содержит цепных правил. Кроме того, цепочка умб является подцепочкой а (поскольку она является кроной поддерева вывода а), и, следовательно, а представима в виде а=рувбе. При этом поскольку высота поддерева с вершиной А не превосходит й, то существует такое д (зависящее только от 6'), что длина кроны умб этого поддерева не превосходит д.
Выводы В=>-»бВп, р=~-*у, п=>-»б могут быть повторены в 6' любое число раз. Поэтому в 6' для любого а=1, 2... могут быть получены выводы 1=»*рВе=~-*1)у"ыб"е и, следовательно, бу"<об"вена. (6') =У.('6). П Из доказательства теоремы 7.4 легко извлечь следующий конструктивный критерий бесконечности: язык Ь(6) бесконечен, если и только если приведенная грамматика 6', эквивалентная 6, содержит такой нетерминальиый символ А, что А=»-*рАп, где либо р непусто, либо и непусто. Действительно, если такой символ существует, то в 6' воз- ззо можны выводы р"Аа" для любого п и соответственно существуют сколь угодно длинные терминальные цепочки, выводимые в 6'.
Если же таких символов в 6' нет, то на одном пути в дереве вывода нетерминальные символы не могут повториться. Поэтому в 6' возможны только деревья высоты, не превосходящей числа нетермииальных символов 6', и, следовательно, язык Е(6)=Ь(6') конечен, Однако содержание теоремы 7А гораздо глубже названного следствия. Она указывает иа периодический характер бесконечности в КС-языках: наряду с любым достаточно длинным словом (1увбе КС-язык обязательно содержит и все слова вида ру"мб"е. Это свойство является необходимым условием бесконтекстности языка; для того чтобы доказать, что язык не является бесконтекстным, достаточно показать, что он не обладает этим свойством. Его можно сформулировать и в терминах длин цепочек: множество длин цепочек КС-языка либо конечно, либо содержит арифметическую прогрессию.
Отсюда сразу следует, что, яапример, язык (а"') не является КС-языком. Рассмотрим теперь некоторые неразрешимые проблемы для КС-грамматик. Основным методом доказательства неразрешимостей в теории формальных языков является сведение к комбииаторной проблеме Поста, которая неразрешима (теорема 6.20). Здесь будет удобно пользоваться слегка измененной формулировкой проблемы Поста (не для пз пар, как в теореме 6.20, а для двух списков длины ш): для списков Х=(аь...,а ) и У=фи...,Р ) цепочек в алфавите 6 решить, существует ли последовательность индексов (о..., (а, такая, что сс;,...
ви, =Ц...Р;, . Пусть алфавит (7 и число т зафиксированы. Введем алфавит (7,=(Ь„..., Ь ), не пересекающийся с (7, и обозначим (7~ =(7()(7м Для списка Х= (яь..., сс ) тп цепочек в алфавите (7 обозначим через Я(Х) множество всех цепочек вида Ь,„.,Ь;рц ...я~„для любых последовательностей индексов 1, ..., 1а, )У)1. Для языков Я(Х) справедливы следующие два утверждения. 1. Если Х=(ио...,и ) и У=((1ь...,р ) — списки цепочек в алфавите (7, то комбииаторная проблема для этих списков имеет решение, если и только если множество Я(Х)()Я(У) непусто.
Действительно, если уенО(Х) и уенЯ~У), то у=Ь;л,... ...Ь;,а,, ..а; .=Ь,ч...Ьй...р;п„р; и, следовательно, я,, и; =В "Фл. 281 2. Для любого списка Х цепочек в алфавите У 11(Х) является КС-языком в алфавите Уь КС-грамматика, порождающая язык Я~Х) для списка Х=(и„...,и ), задается системой 2т правил 7-+Ь||аь 1- -+Ь;и;(1=1,...,т1. Нетрудно видеть, что эта грамматика однозначна. Из этих двух утверждений непосредственно следуют две важные теоремы о неразрешимости. Теорема 7.5. Не существует алгоритма, который по двум произвольным КС-грамматикам 6~ и 6э определял бы, пусто ли пересечение 7 (6~) Д7.
(6,). Если бы такой алгоритм существовал, то можно было бы определить, пусто ли пересечение КС-языков 1;1(Х) и Я(У) для любых списков Х, У, состоящих из и цепочек, откуда следовала бы разрешимость комбинаторной проблемы Поста для данного т, что невозможно. П Теорема 7.6. Не существует алгоритма, который для произвольной КС-грамматикн позволял бы узнать, является ли она однозначной или нет. Язык 1,1(Х), где Х=(ао...,и ), порождается однозначной грамматикой с системой правил Р: )-«-А; А-+ Ь;аб А — ~-Ь;Ааь Язык Я('у), где У= фь..., (3 ), порождается однозначной грамматикой Я».
7-эВ; В-эЬфб В-~-Ь;Врь Язык 1«(Х)()1«(у) порождается грамматикой с системой правил 17«(117». Эта грамматика неоднозначна в том и только в том случае, когда 11(Х)Щ(У) непусто, а это свойство неразрешимо. Из теоремы 7.5 следует, что пересечение КС-языков не обязательно является КС-языком, поскольку для КС-языков проблема пустоты разрешима. Напротив, объединение КС-языков — всегда КС-язык; КС-грамматика для него получается просто объединением правил исходных грамматик. Так как пересечение языков, как и любых множеств, выражается через объединение и дополнение соотношением де Моргана (3.14) в виде 7.Д7»=ГДХ, (см.
«Булева алгебра и теория множеств» в 3 3.2; для языка 7. в алфавите *»' 7.='»"*' Е)1, то отсюда следует, что дополнение КС-языка — не всегда КС-язык. Более того, проблемы распознавания типа языка для пересечения и дополнения неразрешимы. Теорема 7.7. Следующие проблемы для КС-языков неразрешимы: 1) является ли КС-языком пересечение КС-языков; 282 2) является ли КС-языком дополнение к КС-языку; 3) проблема тривиальности КС-языка (7.= У*) нли, что то же самое, пустоты дополнения; 4) проблема эквивалентности двух КС-грамматик.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
