Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Дальнейшие примеры см. в упражнениях 4.9 и 4.11.
Замечание. Легко видеть, что полученное в доказательстве теоремы 4.7 представление обладает следующими свойствами: а) существует система составляющих С цепочки xyz, отвечающая некоторому ее дереву вывода в Г и содержащая отрезок ux2v, соответственно vz\W; б) для каждой цепочки x\unx2vny2z, соответственно xy\VnZ\wnZi, п= 1, 2, ..., существует система составляющих С„, отвечающая некоторому дереву вывода этой цепочки в Г и содержащая любой отрезок, полученный из произвольной составляющей системы С, содержащей отрезок ux2v(vziw), заменой этого отрезка на unx2vn(vnZiWn)\ в частности, сам отрезок unx2vn(vnZxWn) принадлежит Сп (как и все отрезки и1г2и\ соответственно vlZiW\ i^L п).
В заключение параграфа коснемся вопроса о замкнутости класса Б-языков относительно основных операций.
Теорема 4.8. а) Класс Б-языков эффективно замкнут относительно операций объединения, умножения, усеченной итерации и подстановки; б) класс Б-языков не замкнут относительно операций пересечения, вычитания и взятия дополнения.
Доказательство, а) Конструкции, использованные в доказательстве теоремы 1.1 для объединения
134 Б-ГРАММАТИКИ и МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
и умножения, в применении к Б-грамматикам дают снова Б-грамматики. Грамматика, порождающая L(Y)+, получается из Б-грамматики Г, удовлетворяющей требованию леммы 4.2, добавлением правила /—>?// (/ — начальный символ). Доказательство для подстановки предоставляется читателю, б) Незамкнутость класса Б-язы-ков относительно , пересечения следует хотя бы из Ьримера 6 §1.3 и примера 1 настоящего параграфа', поскольку {anbnan\n — 1, 2, .. ,}^{апЬпат\т, я=1,2, ...}П Г\ {etmbnan\m, п—\, 2, ...}. Незамкнутость относительно вычитания и взятия дополнения вытекает из замкнутости относительно объединения и незамкнутости относительно пересечения.
По поводу левого и правого деления см. упражнение 4.12.
§ 4.4. Неоднозначность
Пусть Г — произвольная Б-грамматика. В силу рас-суждений, приведенных в конце § 4.1, множество различных полных выводов в Г распадается на попарно не-пересекающиеся классы, каждый из которых отвечает одному дереву вывода; различие между выводами, принадлежащими одному классу, в известном смысле несущественно. Поэтому введенное в § 3.1 понятие однозначности приобретает в данном случае особенно простой смысл: однозначная Б-грамматика характеризуется тем, что в н%й каждая цепочка порождаемого языка выводима, по существу, единственным способом. (Для произвольных НС-грамматик это не так — см. упражнение 4.5.)
Если некоторый язык порождается неоднозначной Б-грамматикой, то для него, вообще говоря, может найтись Другая Б-грамматика, являющаяся однозначной. (Например, язык {anbm\m, п= 1, 2, ...; ti sg: т <g 2п} порождается неоднозначной Б-грамматикой со схемой {I-*aIB, 1-*аВ, В—*Ь, В-*-ЬЬ) и однозначной Б-грамматикой со схемой {I-^a/bb, I-*abb, I-*-A, A~*-aAb, A-*ab}.) В связи с этим естественно ввести следующее понятие. Б-язык (соответственно ОБ-язык) называется однозначным, если существует хотя бы одна порождающая его однозначная Б-грамматика (соответ-
НЁОДНОЗНАЧНОеГЬ
135
ственно ОБ-грамматика). В противном случае Б-язык называется неоднозначным (или существенно неоднозначным). Цель настоящего параграфа—? указать примеры неоднозначных Б-языков.
Пример 1. Пусть L{ = {anbncm \т, п— I, 2,...}, Ц — {атЬпсп |т., п= 1, 2, .. .}, L = Li\JL2. Язык L порождается, например, грамматикой со схемой {/-^-Л,, /•->Л2, Л,->-Л1с, Ах-^Вхс, Bx^>aBxb, Bx->ab, Л2->аЛ2, Л2->-аВ2, В2~*ЬВ2С, В2 —? Ьс}. Неоднозначность этой грамматики очевидна — всякая цепочка вида апЬпсп имеет в ней два дерева вывода. [Так, для цепочки а3Ь3с3 одно дерево вывода дает систему составляющих (((a (a (ab) Ь) Ь) с) с) с, другое — систему составляющих а(а(а(Ь (Ь (Ьс)с) с))) ] Покажем, что и любая Б-грамма-тика, порождающая L, является неоднозначной.
Пусть Г — такая грамматика. Найдем для нее число s из теоремы 4.7 и положим q = 3sl. Рассмотрим цепочку asbscs+- и применим к ней теорему 4.7 при x — as,
у = bs, z=c+q. Случай б) (из формулировки теоремы 4.7) исключается, поскольку соответствующая цепочка w имела бы вид bk, 0 ^ k < s, или с1, 0 ^ ^ s + 9, а так как v = bl, 0 < г s, мы имели бы либо asbs+i+kcs+4 е L,
либо asbs+ics+q+l eL, но в обеих этих цепочках как степени а и Ь, так и степени бис различны. Поэтому существуют представления bs~yxvy2, asyx=* ххих2, соответствующие случаю а). При этом цепочка и должна, очевидно, состоять либо только из а, „либо только из b; второе, однако, невозможно, так как в таком случае язык L содержал бы последовательность цепочек с постоянными степенями а и с и бесконечно возрастающими степенями Ь. Таким образом, мы получили следующее представление нашей цепочки: asb^cs+4^ = afada8bhbdbmcs+q, где при любом п — 1, 2, ... цепочка
tn=z af+nd+Sbh+nd+mcs+q принадлежит L, и в силу замечания к теореме 4.7 в некоторой системе составляющих цепочки tn, отвечающей какому-то дереву вывода tn в Г, одна из составляющих будет иметь вид and+efoh+nd' ВВИДу Т0Г0) что о < d ^ s и q = 3s!,
