Гладкий - Формальные грамматики и языки - 1973 (947381), страница 43
Текст из файла (страница 43)
Тем самым доказательство будет завершено. Заметим прежде всего, что если ф — произвольная / Р подцепочка какой-либо цепочки из ЕА П Р (Е), сокращающаяся до пустой цепочки, то либо 6Р = 66$а, либо 6р = рт![]уьу, где выделенные вхождения символов 66 н а, й и р, у и у соответствуют друг другу (иначе говоря, сокращаются друг с другом). Действительно, в противном случае мы имели бы ф = и~ай4у~уй; но по опре- Г делению языка ЕА в его цепочке лишь тогда может содержаться подцепочка вида бе, когда б = [В,1,й], е = = [С,1, 1], где символ В левый, а С правый.
Поэтому получаем р = [Р,лб,п] н символ Р оказывается одновременно левым и правым, что невозможно. Пусть теперь ~р ~ЕА() 0 (Е). Если ! 6г != 4 (наименьшая возможная'длина цепочки нз Ел), то ~р ~ЕЛ озна- чает <р=[А, 1, 1]ай[А, Е 1[, причем в Г должно быть правило А-+а с номером 1; но тогда ~р=а, так что Ч~ е Ел. Пусть утверждение доказано для всех цепочек длины, меньшей а (л ) 4), и ~р Ен ЕА Д 0 (Я), причем ! ~р !=е. Тогда ~р=афа', где а= [А, 1, 1], а'= [А, 1', 1']. Нетрудно заметить прежде всего, что выделенные вхождения скобок а и а' соответствуют друг другу, так что а = а'. Действительно, в противном случае, по сделанному выше замечанию, скобка, соответствующая а, стояла бы непосредственно слева от скобки, соответствующей а', т.
е. ~р содержала бы подцепочку [А, Е 1][А, 1', 1']; но тогда А должен был бы быть одновременно левым н правым символом. Далее можно усмотреть, что правило с номером 1 должно иметь вид А- ВС, а цепочка ф должна начинаться символом вида [В, 1, й] н кончаться символом вида [С, 1, 1]. В самом I деле, в силу определения Ел в противном случае могло бы быть только ф = аф'а, причем ф „-а Л, поскольку ! ~р !) 4. Однако тогда выделенные вхождения а и а должны бы были соответствовать друг другу, иначе Г в ф нашлась бы подцепочка аа, чего в цепочке из ЕА быть не может, а значит, ~р' сокращалась бы до Л.
Однако из определения Е' ясно, что 6Р' начинается вхождением а, а значит, при сокращении ф это вхождение сократилось бы с каким-то вхождением а, стоящим правее„что невозможно. Итак, ф=[В, Е й]х[С, 1,!]. При этом  — левый символ, а С вЂ” правый, так что во всяком случае В ~ С, и, значит, скобки [В, 1, й] и [С, 1, 1] не могут быть соответствующими. Следовательно, Х =Ъ, [В, 1, й] [С, 1, 1]ум где у,, и Х, сокращаются до пустой цепочки. Но это означает, что цепочки [В, !', й]Х, [В, 1', й] и [С, 1, 1]Х,[С, 1, 1[ принадлежат соответственно Ез Д Р'(йг) и Ес Д Р (И7); следовательно, по индуктивному предположению они принадлежат Ее и Ес соответственно.
А отсюда — и из наличия в Г правила А — э ВС вЂ” следует, что цепочка ~р = =-[А, 1, 1][В, 1, й]х, [В, 1', й] [С, 1, 1]без[С, 1, 1][А, 1, Д принадлежит Е . 2!6 дополнительные сееденйя о Е.грдь(з(дтикАх !гл.а 2!9 УПРАЖНЕНИЯ Упражнения 6.1. Построить К-грамматики, определяющие: а) язык (хх [х зи (аь ..., а„)1); б) язык [а Ь" [и = 1, 2, ...)'; в) множество ппф логики высказываний в бесскобочной записи; г) язык Лика. 6.2. а) Показать, что для всякой К-грамматики можно построить эквивалентную ей К-грамматику с единственной элементарной натегорией [Г.М. Ильин, не опублнковано1 б) Оценить происходящее при этом увеличение сложности грамматики.
6.3. Оценить увеличение мощности словаря категорий прн построении по данной К-грамматике эквивалентной ей односторонней К-грамматики сложности, не превосходящей 2 (следствне нз теоремы 6.17. 6.4. йоказать, что класс языков, определяемых левосторонннми (нлн правосторонннмн) К-грзмматикамн сложности, не превосходящей 1, «эффектнвно совпадает» с классом А-языков. 6.5. Показать, что класс языков, определяемых произвольными К-грамматиками сложности, не превосходящей 1, «эффектнвво совпадает» с классом линейных Б-языков. 6.6.
Назовем К-гран)катину 0 к а тегор иа льн о о днов н а чн ой, если каждой цепочке языка 5(0) она сопоставляет единственную цепочку категорий, и сннтаксически однозначной, если всякая цепочка ее категорий, сокращающаяся до ее главной категории, имеет единственное дерево сокращения. а) Проверить, являются ли грамматики примеров 1, 2, 3 из 4 6.1 категориально н синтаксически однозначными. б) Пусть Ь' — множество ппф логики высказываний в варианте, рассмотренном в примере 3 из $6.1, но со стертыми скобками.
Построить категориально однозначную, но синтаксически неоднозначную К-грамматику, определяющую )г', таким образом, чтобы для каждой цепочкн нз ь' имелось взаимно однозначное соответствие между ее деревьями сокращения и расстановками скобок, превращающими ее в ппф. в) Показать, что всякая одностоРонняя К-грамматика, обладающая тем свойством, что «знаменателн» всех категорий, являющихся частями элементов значений ее прнписывающей функции, элементарны, синтаксически однозначна. [Заметны, что грамматика, по. строенная при доказательстве теоремы 6.1, обладает указанным свойством.] г) Можно ли распространить результат предыдущего пункта на произвольные односторонние К.грамматики? д) Построить синтаксически однозначные К-грамматини для языков примеров 1 — 3 из 6 4.4.
Показать, что ни один нз этих языков не может быть определен категориально однозначной К-грамматикой. 6.7. Вывести теорему 6А из теоремы 6.2. бдй Показать, что линейный язык (а"'Ь" [т,л =1, 2...4 т ( п) не допускается никакой однодорожечной МП-машиной, удовлетворяющей требованию теоремы 6.4. 6.9. Показать, что для всякой МП-машины, принадлежащей одному нз перечисленных ниже классов, можно построить эквивалентную ей МП-машнну без растяжения, принадлежащую тому же классу: а) класс однодорожечных МП-машин; б) класс чисто стирающих МП-машин; в) класс МП-машин с ограниченным числом поворотов. 6.16.
Назовем дерево подчинения для правильно построенной формулы узкого исчисления предикатов в бесскобочной записи «естественным», если оно построено, как в следующем примере: Постронть для множества формул указанного вада Д-грамматику, сопоставляющую каждой из ннх естественное дерево подчинения (и только его). 6.11. Показать, что Д-грамматика, получаемая из К-грамматики 0 при обратной иерархизации, нмеет ограниченную ширину, а при прямой иерархизации, если язык й(0) бесконечен,— неограничен.
ную. 6А2. Показать, что Л-грамматика, получаемая из К-грамматики сложности 1 при прямой иерархизация, имеет высоту 1, а при обратной иерархизации — ширину 1. 6.13. Г1оказать, что длины путей без ветвления *) в деревьях подчинения, сопоставляемых цепочками К-грамматикой 0 при прямой иерархизации, не превосходят сложности 0 [Е. И. Подольская, не опубликовано]. 6.14. Назовем Л-грамматику 0 = (Г,[) однозначной, если никакой цепочке она не сопоставляет более одного дерева подчинення Соответствующую функцию [ будем называть «строгой», если все ее значения — одноэлементные множества, Р!сследовать взаимоотношение между однозначностью 0 и строгостью [.
6.15. Построить однозначные Л-граммзтикн (упражнение 6.14) для языков прнмеров 1 — 3 яз $4.4. 6.16. Показать, что всякая приведенная удлиняющая Б-ОАЕВ- грзмматнка (6 5.4) имеет конечную степень. 6.17. Показать, что любая приведенная удлиняющая Б-граммах тика, порождающая язык (и"Ь" [п = 1, 2, ...), имеет конечную степень. 6.18. Пусть à — НС-грамматнка без правил вила срАф-»~РВф, А,В и йг, и фАф-»фаф, А щ йг — (7), аш У. [Такие грамматики по. Рождают не все НС-языки (см. теорему 3.7), но н не только Б-языки (достаточно слегка видоизменить пример 1 кз $3.4).] а) Обобщить определение Л-грамматики на случай, когда ее — нс )П»,ь..., „„„„„, „Юу„„„„„,„ у'лам аь,.„а~ подчннены только аз, ..., агю соответственно, 2я) дополнительные Сведения О в-гплммлтиклх !Гл. а.
б) Показать, что при таком обобщении сохраннет силу пункт а) леммы 8.2. 8.16. а) Показать, что решение нормальной системы уравнений единственно, если ни один нз членов левых частей не равен одной нз переменных $~ или произведению нескольких переменных. б) указать примеры, из которых следует, что при нарушении одного из условий пункта а) утверждение этого пункта теряет силу. 6.26. В пространстве формальных рядов в данном алфавите опре- делить расстояние таким образом, чтобы это пространство стало мет- рическим.
6.21. Показать, что пространство формальных рядов в данном алфавите является полным (т. е, в нем имеет место критерий Коши). 622. Определим сложение, ум нож спи е и ада м а рова у м н о ж е н и е формальных рядов (обозначения: +, Х и ® соответ- отвеина) следующим образом: если г= ~чР~ 7(п) х„, э = ~ч ~, д (и) х„, п=с п=о Э Ш то г+ з ~~ (1 (п) + к (п)) х„, гХз ~я~~ й (п) х„, где й(п) — сумма и э л=э всевозможных произведений 1(!) Л(!) таких, что х!х! — — х„, г3з ~чР~ 1(п) я(п) х„, Показать, что опорные множества радов г-(-з, п=с гХ з и гэз равны соответственно объединению, произведению н пересечению опорных множеств г и э.
6.23. Показать, что дополнение к языку Дика 0(У) можно представить ввиде 3(Е',ап ..., а„, ап .. ° ап~а~0(У),, апР(1') аг0 (У), ..., а„0 (У)), где (а,,..., а„) = У и 1.' — стандаРтный А-Язык в словаре (ао ..., а„, аь ..., азп). Аналогично для скобочного языка.. 6.24. Построить детерминированные МП-машины, допускающие языки 0(У), СР(У), 0'(У) и СР'(У) соответственно.
6.26. а) Показать, что теорема 87 останется справедливой, если взять в качестве Г линейн~ю Б-грамматику и заменить 0(л) н Р'(л) языками Р!(л) и О! (л) соответственно, где 0,(Х) . г и 0 (л) определяются следующим образом: (!) Л сн О, (л), Лсм0,(л); (!!) если хщ0!(л), х щ0! (л) и аеэУ, то аха, г l лхагв0!(л), ах дсн0!(2); (Ш) никакая цепочка не может при- надлежать О!(л) или О, (л) иначе, как в силу (Ц или (!!). б) Сформулировать и доказать аналогичные утверждения для металинейиых Б-грамматик, итерационно-линейных Б-грамматик и ,Б-ОАЕВ-грамматик, 8.26. Показать, что если в теореме 8.7 вместо стандартности .языка Е' потребовать выполнения более слабого условия — й-опреде.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
