Гладкий - Формальные грамматики и языки - 1973 (947381), страница 27
Текст из файла (страница 27)
Поскольку а4 ( а4 и обе эти точки расположены в отРезке у, для подходящнХ у~ И Ут имеем у=У,оум х'=хуь 1твгт = утг; при этом о чь Л. Если теперь положить (74 = Ть (7„+4 = БНЬ(У„, Тм Т,), то при любом и = = 1, 2, ... (7„ будет (В, о"(ти4")-деревом, а Т„ = = БНЬ(Т, Т„ (7„) будет (1, ху,о"1тп4"гз)-деревом, где ! — начальный символ Г, так что ху4о"1гтв"гт еи Е. Та- ким образом, положив г, = 1м получаем искомое представление. Пример 4. Пусть Е=(а"Ь"а'"]п4, п=1, 2, ...; п4 = п), Теоремы 4.5 н 4.6 к языку Е неприменимы; действительно, требуемое теоремой 4.5 представление цепочки а Ь"а'" получается при х4 = а"-', у, = а, г = Л, у, = Ь, хт = Ь"-'а'", и К(Е) = (р (1, 1)+ц (2, 1)+ + (2 1) ]Р ч = О, 1, ...).
В то же время теорема 4.7 позволяет установить, что Š— не Б-язык, Именно, если бы цепочка а"Ь"а, лч ( и, допускала требуемое этой теоремой представление при х = а" Ь", у = а, г = Л, то цепочка и или гв во всяком случае состояла бы либо целиком из а, либо целиком из Ь; но если бы она при этом была пуста нлн содержалась в у, то язык Е содержал бы любые цепочки вида а"Ь"а"'Р44, где с ) 0— постоянная и 4' = 1, 2, ..., а в противном случае в 1. нашлась бы цепочка вида аРРа', где р Ф д.
Дальнейшие примеры см. в упражнениях 4.9 и 4.11. За меча н ие. Легко видеть, что полученное в доказательстве теоремы 4.7 представление обладает следующими свойствами: а) существует система составляющих С цепочки хуг, отвечающая некоторому ее дереву вывода в Г и содержащая Отрезок ихзо, соответственно ог4п4; б) для каждой цепочки х4и"хто"утг, соответственно ху,о"г4и4"гм и = 1, 2, ..., существует система составляющих С, отвечающая некоторому дереву вывода этой цепочки в Г и содержащая любой отрезок, полученный из произвольной составляющей системы С, содержащей отрезок ихто(ог4и4), заменой этого отрезка на и"хто" (о"г4Ш"); в частности, сам отрезок и хто" (о г,гв") принадлежит С, (как и все отрезки и'г,о', соответственно О4г44В4, 4 П).
В заключение параграфа коснемся вопроса о замкнутости класса Б-языков относительно основных операций, Т е о р е м а 4В. а) Класс Б-языков аффективно замкнут относительно операций объединения, умножения, усеченной итерации и подстановки; б) класс Б-языков не замкнут относительно операций пересечения, вычитания и взятия дополнения. Доказательство. а) Конструкции, использо4 ванные в доказательстве теоремы !.1 для объединения [34 В-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОИ ПАМЯТЬЮ [ГЛ.
4 ИноднознАч[щсть' 4 4.41 н умножения, в применении к Б-грамматикам лают снова Б-грамматики. Грамматика, порождающая Е(Г)+, получается из Б-грамматики Г, удовлетворяющей требованию леммы 4.2, добавлением правила 1- 11 (1 — начальный символ). Доказательство для подстановки предоставляется читателю. б) Незамкнутость класса Б-языков относительно, пересечения следует хотя бы из Примера 6 $1.3 и примера 1 настоящего параграфа', поскольку (а"Ь"а" [и=1, 2, ...)=(а Ь"а" [и, п=1,2, .)П П (а Ь"а" ~ и, и = 1, 2, ...). Незамкнутость относительно вычитания и взятия дополнения вь[текает из замкнутости относительно объединения и незамкнутости относительно пересечения. По поводу левого и правого деления см.
упражнение 4.12. 5 4.4. Неоднозначность Пусть à — произвольная Б-грамматика. В силу рассуждений, приведенных в конце З 4.1, множество различных полных выводов в Г распадается на попарно непересекающиеся классы, каждый из которых отвечает одному дереву вывода; различие между выводами, принадлежащими одному классу, в известуом смысле несущественно.
Поэте[Ау введенное в З ЗЛ понятие однозначности приобретает в данном случае особенно простой смысл: однозначная Б-грамматика характеризуется тем, что в ней каждая цепочка порождаемого языка выводима, по существу, единственным способом. (Для произвольных НС-грамматик это не так — см. упражнение 4.5.) Если некоторый язык порождается неоднозначной Б-грамматикой, то для него, вообще говоря, может найтись другая Б-грамматика, являющаяся однозначной. (Например, язык (а"Ь'"(и, и = 1, 2, ...; п < т < 2п) порождается неоднозначной Б-грамматикой со схемой (1 — а1В, 1- аВ, В- Ь, В-~ЬЬ) н однозначной Б-грамматикой со схемой (1- а1ЬЬ, 1- аЬЬ, 14-А, А-4-аАЬ, А- аЬ),) В связи с этим естественно ввести следующее понятие.
Б-язык (соответственно ОБ-язык) называется о д н о з н а ч н ы м, если существует хотя бы одна порождающая его однозначная Б-грамматика (соотзет- отвеина ОБ-грамматика). В противном случае Б-язык называется неоднозначным (нлн существенно н е о д н о з н а ч н ы м). Цель настоящего параграфа— указать примеры неоднозначных Б-языков. Пример 1. Пусть 1.,=(а"Ь"с 1и, п=1, 2, ...), Е,=(а Ь"с" [т, п=1, 2, ...), 1.=1.,()Е,. Язык Е порождается, например, грамматикой со схемой (1-+Аь 1 — + А„А, -+ А с, А, -+ В, с, В, -+ аВ, Ь, В, — + а Ь, А, — аА», А, -+ а„» — ЬВ,с, В„. Ьс). Неоднозначность этой грамматики очевидна — всякая цепочка вида а"Ь"с" имеет в ней два дерева вывода. [Так, для цепочки а»Ь»сз одно дерево вывода дает систему составляющих (((а(а(аЬ) Ь) Ь) с) с) с, другое — систему составляющих а(а(а(Ь(Ь(Ьс)с)с))).) Покажем, что н любая Б-грамматика, порождающая Е, является неоднозначной.
Пусть à — такая грамматика. Найдем для нее число з из теоремы 4.7 и положим а=За!. Рассмотрим цепочку а'Ь'с'+4 и применим к ней теорему 4.7 при х=а', у = Ь', а=с'+4. Случай б) (из формулировки теоремы 4.7) исключается, поскольку соответствующая цепочка и[ имела бы вид Ь», 0~(й < з, или с', 0~(1<а+ д, а так как о = Ь', 0 < 1~ ~з, мы имели бы либо а'Ь*+'+ с'+4 ен Е, либо а'Ь'+ с*+"+' ен Е, но в обеих этих цепочках как степени а и Ь, так и степени Ь и с различны. Поэтому существуют представления Ь'=у,оуь а'у, х,их», соответствующие случаю а). При этом цепочка и должна, очевидно, состоять либо только из а, „,либо только из Ь; второе, однако, невозможно, так как в таком случае язык Е содержал бы последовательность цепочек с постоянными степенями а н с и бесконечно возрастающими степенями Ь.
Таким образом, мы получили следующее представление нашей цепочки: а Ь с Я »Я+4 = а[а~ахЬ"Ь Ь с'+', где при любом и =1, 2, ... цепочка 1„= а[+"а+ЯЬ"+"~+ с'+4 принадлежит Е, н в силу замечания к теореме 4.7 в некоторой системе составляющих цепочки 1„, отвечающей какому-то дереву вывода [„в Г, одна из составляющих будет иметь вид а~~сЬ"+"~. Но ввиду того, что 0 < 44 =.
з и д = Зз1, найдется такое пь что 41 пя[Е Имеем тогда 1~,+[ 1йв в-1'Рлммлтики и млшииы с млглзиннои плмятью 1Гл. 4 млшииы с млглзинноп плмятью 137 =а""«+"'Ь""'"""с"«=а+«Ь+«с'+«и для некото рого дерева вывода Т цепочки а'+"Ь*+«с'+' в Г одна из составляющих соответствующей системы С будет иметь вид а"+«Ь'+ . Теперь мы можем, рассматривая цепочку «+« «+л а*+«Ь'с* и рассуждая так же, как раньше (с точностью до зеркальной симметрии), найти такое дерево вывода Т' той же цепочки а +«Ь'+«с'~«в Г, что одна из составляющих соответствующей системы С' будет иметь вид . Ь"+л с«+« . Поскольку Ь, Ь' ( з < д, составляющие а"+«Ь"+ и Ь«~ с«+«пересекаются; поэтому системы С «+««+л »+л «+«' и С', а значит и деревья Т и Т', различны.
Пример 2. Пусть й! = (хйхЬу)х, учи(а»,аз)«), Т.з = 1хЬуЬу)х, у е= (а4, аз)+), Т, = Т.! О (.з. Построение Б-грамматики, порождающей з., не представляет труда. Если à — произвольная Б-грамматика, порождающая Т., то, определив з и 4), как в примере 1, рассматривая цепочки а;Ьа;Ьа»+' и а;+«Ьа;Ьа', и рассуждая в точности так же, как в предыдущем примере, мы найдем два различных дерева вывода цепочки а;+«Ьа;+"Ьа',+'. Пример 3. Пусть 7.! = (а«Ьла"Ь'")Ь, и, л=1, 2, Т.з = (алЬ"а'"Ь')й, »и, а = 1, 2, ...), !.
= л.! () 1.з и Г— Б-грамматика, порождающая Т.. Определив з и д, как в примере 1; рассмотрев цепочку а»Ь»ФЬ»+«и рассуждая, как в предыдущих примерах, мы без труда найдем для цепочки ! Г = а»+«Ь*а»4 «Ь»««такое дерево вывода, что одна из составляющих соответствующей системы будет иметь вид аз»«Ь»ал+«. Применим к цепочке 1 теорему 4.7, положив х = а»+«, у = Ь', х = а»4 «Ь»+«, Аналогично предыдущему легко видеть, что соответствующая цепочка и .нли и» не содержит вхождений а. Если прн этом она содержится в «правой Ь-зоне», то цепочка 1 имеет две частично пересекающиеся составляющие и, следовательно, два различных дерева вывода. Остается случай, когда и или и», так же как и с, содержится в «левой Ь-зоне».
Тогда цепочка их»о или сг»и» будет иметь вид Ь', 0 =1 = а, и при подходящем п, цепочка и" "'х,с"»+' или о" +»я»зс"+! совпадет с цепочкой Ь+«. В силу замечания к теореме 4.7 отрезок цепочки Г„, =а'+«Ь'~«а'+'Ь'+«, полученный из отрезка а«4.«Ь»ал+«цепочки 1 заменой Ь' иа Ь4+«, будет составляющей цепочки Г„, в некоторой системе, отвечающей какому-то дереву вывода 1,, в Г. Таким образом, некоторое дерево вывода Т цепочки 1„, дает составляющую А, начинающуюся левее конц а «левой а-зоны» и заканчивазощуюся «в правой а-зоне». Теперь мы можем, рассуждая симметрично, показать, что либо цепочка у = а»4«Ь»4«а»Ь»+«имеет два различных дерева вывода, либо некоторое дерево вывода Т' той же цепочки 1,, дает составлящую А', начинающуюся в «левой Ь-зоне» и заканчивающуюся п р а в е е н а ч ал а «правой Ь-зоны».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
