Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 55
Текст из файла (страница 55)
Выводимость р из а обозначается а~"5 (если нужно указать длину вывода) или а=~-»5 (если длина вывода не указывается). Языком 1.(6), порождаемым грамматикой 6, называется множество всех цепочек в терминальном алфавите У, выводимых из 1. Грамматики 6 и 6' эквивалентны, если Ц6) =1.(6'). 263 В теории грамматик сложились свои традиции обозначений, которых мы будем придерживаться. Символы терминального алфавита принято обозначать малыми латинскими буквами, символы нетерминального алфавита— большими латинскими буквами, цепочки в алфавите У())У вЂ” греческими буквами. Длина цепочки и обозначается 1(а) или ~я~. Множество всех цепочек в алфавите У обозначается, как и прежде, У'; множество всех непустых цепочек обозначается У+.
Иногда принятые здесь обозначения расходятся с традициями теории формальных систем — например, приведенные выше обозначения для выводимости (вместо использованного в 5 6.1 — 6.4 знака ) — ). Понятие формальной грамматики практически совпадает с введенным в $ 6.4 понятием системы подстановок (полусистемы Туэ). Правда, множество, порождаемое подсистемой Туэ, — это множество ее заключительных слов, а при отсутствии ограничений на правила вывода в грамматике 6 цепочки языка Е(6) могут не быть заключительными.
Однако это обстоятельство не является существенным ввиду следующей леммы. Лемма 7.1. Для произвольной грамматики 6 существует эквивалентная ей грамматика б„левые части правил которой не содержат вхождений основных символов. Пусть 6= ( У, В', )г, 7 ). Каждому символу аенУ поставим в соответствие двойник — символ А, не содержащийся в У()1Р; множество всех двойников обозначим У'. Определим теперь 6,= ( Уь 1Гь Рь 7~ ) следующим образом: У~ — — У, 7~ — — 7, Ю',=Р0У', а Р,=Р'()Р", где Р'— множество всех правил вида А- а (аенУ, А — двойник а), а Д" получено из 1с заменой в каждом правиле всех вхождений терминальных символов вхождениями их двойников.
Каждому выводу 7, зь ..., а в 6 соответствует вывод е,',...,е„, з„'+,, ..., е„'+,„в 6', где е,.(1(л) получено нз е, заменой всех символов из У их двойниками, а е„'+(у~т) получено нз е +у ~ применением правила из Р', причем к е„ч правила из )с' уже неприменимы. Ясно, что а„+ =е., поэтому 1.(6) ы1.(6,). Поскольку только правила из Р' содержат терминальные символы в правых частях, то любой вывод из 6~ цепочки длины гл должен содержать т применений правил из 1с'.
Удалив из вывода применения этих правил и приведя в нем обратное переименование двойников в символы У, получим вывод этой же цепочки в 6. Отсюда 1.(6,)ыЬ(6), и, следовательно, Е(6) =Е(6~). П Прием введения двойников, только что г)родемонстрпрованный при исследовании грамматик, является весьма распространенным. Сама же лемма позволяет утверждать, что для любого языка Е, порожденного некоторой формальной грамматикой, существует порождающая его грамматика, для которой  — множество ее заключительных слов в смысле $6.4.
Используя это утверждение и теорему 6.15, нетрудно доказать следующую теорему. Теорема 7.1. Для любого перечислимого множества. М существует грамматика О, такая, что М= — 1.(В). П Отметим, что эта теорема не является непосредственным следствием теоремы 6.15, поскольку не всякая система подстановок является грамматикой; преодоление этой небольшой технической трудности предоставляем читателю. Итак, формальные грамматикя являются частным случаем полусистем Туэ, и при этом они способны порождать любые перечислимые множества. Поэтому, рассматривая грамматики общего вида, мы не выходим за пределы общей теории формальных систем (см. $ 6.4).
Специфика формально-лингвистического подхода к описанию множеств цепочек начинает проявляться при рассмотрении более узких классов грамматик. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматпк, Грамматика типа Π— это грамматика произвольного вида, без ограничений на правила вывода. Грамматика типа 1, или контекстная грамматика — это грамматика, все правила которой имеют вид аА1) — эавр, где ы~(г'()Ф')+. Цепочки а и р — это контекст правила.
Опи не изменяются прн его применении. Грамматика типа 2, или контекстно-свободная (КС-) грамматика, — грамматика, все правила которой имеют вид А — ~-а, где иен (Щ() Ф') *. Грамматика типа 3, илн регулярная грамматика, — грамматика, все правила которой имеют вид либо А- аВ, либо А- а. Язык Е называется языком типа 1(1=0, 1, 2, 3), если существует порождающая его грамматика типа й Пример 7.1.
а. Множество нечетных чисел в упарном представлении (пример 6.7,а) — это множество цепочек вида а, ааа, ааааа ..., т. е. язык (а'"-'). Он порождается грамматикой 6= ( У, Ф, 77, 7 ), где )'=(а), 11т=(7, а), а Л содержит правила; 7-э а; 7 — эаа7. Из вида правил непосредственно следует, что язык имеет тип 3. В последующих примерах грамматик алфавиты )/ и ((»» не будут указываться в тех случаях, когда принятые нами обозначения терминальных и нетерминальных символов позволяют однозначно извлечь эти алфавиты из правил. б. Язык (а"Ь") является КС-языком (языком типа 2), поскольку он порождается КС-грамматикой с двумя пра.вилами вывода: 1- а1Ь и 1-~аЬ. в.
Язык булевых формул с переменными а, Ь, с порождается КС-грамматикой, где У=(а, Ь, с, '»/, Ь, ~, (.)); %'= =(1); Л содержит правила: 1-». (1 ~/ 1); 1 »- (1 8с 1); 1 — ~1; 1- а; 1-»- Ь; с. Этот язык отличается от языка формул исчисления высказываний (пример 6.7, б) отсутствием импликации. г. Если в предыдущем языке последние три правила, вводящие операции ~/, й, „заменить четырьмя правилами, вводящими операции "+, —, °, ", то получим язык арифметических выражений.
Этот язык отличается от обычного языка арифметических выражений тем, что не учитывает ассоциативности сложения и умножения, а также приоритетов операций, и поэтому его выражения содержат слишком много скобок (аналогичное замечание относится н к языку нз примера «в»). Волее близкий к обычному язьпс арифметических выражений с переменными а, Ь, с задается более сложной КС-грамматикой: 1-»- Т; 1-».1+ Т; 1-»- 1 — Т; Т-~ М; Т вЂ” ». Т ° М; Т вЂ” Т1М; М -~ (1); М вЂ” ~К; К-э а; К-~Ь; К- с. Лля полного совпадения с обычным языком арифмети- ческих выражений в эту грамматику надо добавить прави- ла, порождающие числовые константы и произвольнгае идентификаторы переменных, что мы предоставляем чита- телю.
д. Язык а"Ь"с" порождается следующей грамматикой: У-+ аВа; В-~- аВСа; В-+-Ь; ЬС-+ ВВ; аС-+ Са. Эта грамматика не является контекстной (из-за послед- них двух правил), однако можно убедиться, что ей эквива- лентна следующая контекстная грамматика: !-+ АВА; В-+ АВСА; В -+.
Ь; ЬС -~- ЬЬ; АС вЂ” РС; РС- РА; РА — СА; А — эа, в которой неконтекстное правило аС-+.Са заменено четырь- мя контекстными правилами, а А играет роль двойника а (см. доказательство леммы 7А). Поэтому язык (а"Ь"а") имеет тип 1. Связь языка с порождающей его грамматикой имеет ту же природу, что и связь функции с вычисляющим ее алго- ритмом, о которой говорилось в комментарии к теореме Рай- са (см. гл. 5).
Поэтому проблемы распознавания свойств языка по свойствам задающей его грамматики часто ока- зываются алгоритмически неразрешимыми, В частности, как будет показано ниже, неразрешима проблема распознавания эквивалентности двух грамматик (разрешим лишь ее частный случай, когда обе грамматики имеют тип 3 — о нем будет сказано в гл.
8); неразрешима также проблема: для языка типа 1 определить, является ли он языком типа 1' для 1)й Как обычно, неразрешимость алгоритмической проблемы в целом не исключает разрешимости ее для конкретных случаев. В частности, для всех 1=0, 1, 2 имеются примеры языков типа й для которых доказано, что они не являются языками типа 1+1, Эти доказательства опираются, как правило, на некоторые необходимые (но недостаточные!) условия принадлежности языка к определенному типу.
Некоторые из этих условий будут приведены ниже. Грамматики, в которых все правила обладают тем свойством, что их левые части не короче правых, называются неукорачивающими, поскольку в любом выводе такой грамматики'длины цепочек могут только возрастать. Теорема 7.2. Если 6 — неукорачивающая грамматика, то язык Т,(6) разрешим. Пусть аенй(6) и 1а)=п. Если вывод а имеет вид 1, ...
(3,7, ...,(3, ..., а, т.е. некоторая цепочка повторяется,то,удалив нз вывода последовательность у, ..., (1, снова получим последовательность, являющуюся выводом сс. Следовательно, для любой цепочки а~7.(6) существует ее бесповторный вывод в 6, т. е, вывод, в котором все цепочки различны, причем ввиду того, что 6 — неукорачивающая грамматика, длины цепочек в выводе не превосходят и. Число г(п) таких цепочек ограничено: г(п) ( "р„()г())г')', и, следовас=~ тельно, длина бесповторного вывода цепочки ц длины и не превосходит г(п)!.
Поэтому для любой цепочки ы алгоритм распознавания принадлежности ее Е(6) заключается в том, чтобы перебрать все бесповторные последовательности це. почек длины (и, оканчивающиеся цепочкой ы (число которых ограничено величиной з (а)), и для каждой из них проверить, является ли она выводом в 6 (сложность проверки также ограничена, так как она заключается в проверке для каждой пары соседних цепочек рь (),+ь получается ли ()ы, из (); применением некоторого правила 6). В действительности справедливо более сильное утверждение — языки, порождаемые неукорачивающими грамматиками, примитивно рекурсивны. Очевидно, что все контекстные грамматики являются не- укорачнвающнмн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
