Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 34
Текст из файла (страница 34)
Тогда р п у принадлежат писпущей после- довательности для д', и после каждого из них стоит з. Отсюда заключаем, что р=г. Так как правила А — С н В С оба являются правилами типа 3, то р'=г'. Иначе говоря, пусть 8 †функп переходов ДМП-автомата М, по которому была построена грамматика 6. Тогда б(р,е, 2) = (з, Ув) для некото- рого 1', и б(з', е, У) =(р', е) =-(г', с). Позтолсу Л.-В и Лх=-.В». Оя гл. г теогия лгтсеминшовлииого Рлзаогз Случай Х =5 рассматривается аналогично с той лишь раз.
ниной, что роль ц' играет начальное состояние ц, ДМП-авто- маза йй (З Лемма 8,11. Грамматика 6, из алгоритма 8.5 обладает тело же тремя сеойстволи, «то и грамматика 6, из,ммлы 8.!О. Доказательство. Свойство (1) опять доказывается простой индукцией. Чтобы доказать (2), заметим, что на шаге (2) алгоритма 8.5 не возникает новых правых частей и, следовательно, новых пар, связанных отношением ' . Кроме того, каждая празовыводимая цепочка в 6, прввовыводима и в 6, а потому легко показать, что не возникает и новых отношений се и зз. Для доказательства (3) достаточно показать, что если праоило А» В„ принадлежит Р„ то Вх не встречаетси в праной части никакого другого правила и, значит, является бесполезным символом, который' удаляетсв иа шаге (2б). Нам уже известно, что в Р, пет правила С„Вх, если Сна А. Нов>южны только правила Сх Вхо, Сх Вху>з и Сг ХКВх.
Далее, А В— правило типа 3, и потому если В=[цц'[, то ц' — состояние стирания. Таким образом, в Р, нс может быть правил Сх В„а и Сх ВхВт поскольку С Ва и С В †прави типов 2 и 4 соотвежтвевио. Рассмотрим правило Сг ХгВх. Пусть Х=[рр) и А=[гР[ Т 'огда ц — второе состоннис в пйпзущей последовательности для р', потому что С Х †прави типа (4). Кроме того, поскольку А  †прави типа 3, ц следует ва г в лкбой пишущей последовательности, где встрсчаезся г.
Но так как Х в правовыводимой пепочкс в 6, стоит непосредственно слева от А, г встречается в пишущей последовательности длн р', причем г,ьр'. Таким образом, в пишущей последовательности для р' состояние ц попадается дванщы, что невозможно. Д Лемма 8.12. Грамматика 6, из алгоритма 8.5 об,шдиелз >ломи жг тремя свойсизвомо, юпо и гралиотоха 6, из лгммы 8.10, Д о к а в з т е л ь с т в о. Свойство (1) снова доказывается „в лоб". Для доказательства (2) заметим, что если Х и г' связаны в 6, одним из отношений ю '. Яли ТР, то Х и Г, представляющие собой Х и 1' с отброшенными верхниии индексами (если онв были), точно так же связаны в 6з Таким образом, 6,— грамматика (1,1)-предшествования и свойством (2) обладает.
Свойство (3) очевидно. С) Теорема 8.17. Громлотияа 6, из алгоршлла 8.5 является обратимой громлотихой (2,1)-лредшгствоваиил. !во а з ГРлммлзики, поРОждхющиР лез еРминиРоалниые языки Доказательство. Так как Р, для каждого а из З содержит пе более одного правила вида А — а, то ясно, что грамматика 6, обратима. Легко иоказатзь что новые конфликты отношений (1,1)-предшествовапия могут возникнуть только для новых связей: (1] Ах ЗРЬ и (2) Скц Ах. Конфликты вида (1) новинка>от из-за того, что в 6, выполннются некоторые из соотнозпепий ВЬУР5 нли Вф Ь и, кроме того, Вг=>о Ах.
В 6„а значит, и в 6, могут выполняться также соотношения Лх Ь нли Ах(Ь, Конфликты вида (2) обусловлены сходными причинами, В 6, могут выполняться соозношения С вЂ ' Вс или Сс( Вс, и, кроме того, Вс,:М А'„. В 6„а значит, и в 6, возможно также С вЂ” 'Ах. (С' — это С без индексов.) Покажем, что ззотенцивльные конфликты вида (1) разрешаются с помощью отношение (2,1)-предшествования, Конфлякты вида (2) невозможны. Случай 1: Предположим, шо СА"„в Ь в 6, для некоторого СЕВ> и клк в В„так и в 6, либо СЛх Ь, либо СА>з«ХЬ. Тогда С=-Хх для некоторых 2 и й) последнего символа в действителызости может и не быть. Заметим, что, поскольку Лх ЗР Ь выполняется в 6„но пе выполняется в В„должен найтись такой вынод Вф =>о А;з, что С в правом выводе з грамматике 6, появляется слева от В"„, Поэтому у = Х.
Теперь нужно показать, что в Кг не может быть двух разных нетерминалов Вх и Ах. Другими свозами, в Кз нет таких Вх и А., что А4=В, А=зов, В=зов. Пуст~ А.=[цц'[, В=[рр'1 и Х=[гг'[. Заметим, что ц и р принадлежат пишущей последовательности для г'. Кроме того, если [зз'[=>ои и [зз")=зйа, то, рассмотрев ДМП-автомат, лежащий в основе 6, заключаем, что з' =. з'. Таким образом, ц' однозначно определяется состоянием ц, а р' †состояни р, при условии что [цц [ =Ьоа и [рр [='5иа. Окзо>та след)ет, что поскольку ц и р принадлежат пишущей последовательности для г' и ц ~ р, то либо В встречается в качестве выводимой пеночки в выводе А ~да, либо А встречается в выводе В=зов.
Без потери общности предположим, что осу«зсствляется пер. вая возможность. Тогда в 6 существует нетривиалызый вывод В из Л, и в нем применяются только правила типа (3). Поэтому Лх-— -зд Вх, и символ Вх должен был быль удален на шаге (2) алгоритма 8.5. Таким образом, заключаем, что в 6, нет симво,>а Вг. Случай, когда вместо С в приведенном выше рассуждении стоит 5, рассматривается аналогично.
Здесь роль г' будет играть начальное состояние соответствующего ДМП-автомата ц,. Случаи 2: Допустим, что для некоторш'о С в 6, выполняется соотношение С с( Ах, а в 6„ и в 6, †соотношен С ' Ах, Тогда звз гл л. теогня Летсгминигованного я»запел найдется такай символ В», что Се В'„нлн С ' В' в 6, А' . '„в л и Вх~о, » Рассуждая, как в случае1,заключаем, что С=Х2 и А»=во В» нли наоборот. Таким образом, А» илн В» были улалены на шаге 2 алгоритма 8.5. Заметим, что здесь не может быть конфликта о гношеннй (1,1]-предшест вованна и тем более (2,1]-пред. шествования.
Отсюда заключаем, что 6, †обратим грамматика (2,1)-предшествованпя. [3 Следствие 1. Каждый детгр чикироеаккый язык С, обладоюгиий префикгиыл шойстеом и не содержшций е, иыжт обратимую граммапшку (2,!)-предшествования. Д Следствие 2. Вело !.ж2'- детерминированный лзык и 4 ке прикид»сжиш 2, то яник 54 ичееш обратимую гралматпку (2,1)-пргдшешпвозакия. Г Теорему 8.!7 можно усилить, отбросив концевой маркер, )помян]тый в слелствии 2. Теорема 8.18. Каждый детерлгикирозаккый язык, ке содержа- и(ий е, имеет обратимую гршимитику (2,1)-предшестеозшшя. Доказательство.
Пусть йй имеет каноническую грамматику 6. Применим к 6 алгоритм 8.5, а к полученной грамматике 6,— алгоритм 8А. Мы утверждаем, чта грачлгатпгга, по. строенная алгоритмом 8.4, также является обраюгмой грамматикой (2,1)-предшестмзвания. Доказательство оставляем в качестве упражнения. (-) упважненмя 82.1. Постройте ДМП-автоматы в нормальной форме дону.
екающие (в) (мсшя)юЕ(афб)"), (б) (а Ь"а"Ь !ш, и ра 1), (в) 5(6,). 8.2.2. Найдите каноническую грашяатику для ДМП.автомата в нормальной форме Р=((ц ц ц цл ц/) (О 1) (Я. 71 Х), б, 4„7„(цг)) где б для всех )' определяется равенствами б (ц„е, У) = (4„7, !') 6(ц,, О, У]=(ц„У] 6(ц ° ! У)=(ц, !') 6(ц„г, У) =(цо Х!') 182 »пелжпепия б(цо е, Х) =(ц„е) б(ц„е, 7,) = (цп е) 6(ц„е, Ел) =(цр е)') 8.2.3.
Найдите в упр. 8.2.2 состонпия записи, чтения и стирания. 8.2.4. Дайте формальное доказательство теоремы 8.9. В следующих трех упражнениях имеется ванду каноническая грамматика 6 =(Р), 2, Р, В), 8.2.5. Покажите, что (а) если цц' айР, то ц — состояние чтения, (б) если цц' (рр )айр, то р — состояние чтения, (в) шли [цц') [рр')ЕР, то ц — состояние записи, а р" — состояние стирания, (г) если [цц ) [рр )[гг') 5 Р, то р' — состояние записи, а г'— состояиие стирания. 8.2.8. Покажите, что если [цц')[рр'! встречается в качестве надцепочки правовыводимой в 6 цепочки, то (а) ц' — состояние ааписи, (б) ц'чьр, (в) р принцдлсжит пишущей последовательности для ц'.
8.2.7. Покажите, что если [цц')=о+ а[рр'], то р' — состояние стирания. 8.2.8. Докажите необходимость условия в теореме 8.10. 8.2.9. Дайте формальнос доказательство теоремы 8,15. 8.2.!О. С помощью алгоритма 8Л найднтс обратимые грам- матики (2,1]-цредшествования для следующих детерминированных языков: (а) (аО сО")и)0) Б(ЬОосОт" (и мжО), (б) (О а!"О )п)0, ш)0) 0(0 Ь) "0")п)0, ш -О). 8.2.11.
Рассмотрите полностью случай Х=-5 в лемме 8.10. 8.2.12. Закончите доказательство теоремы 8.17. 8.2,13. Докажете теорему 8.18. *8.2А4. Покажите, что КС-язык имеет Ы(0)-грамматику тогда и только тогда, когда он детерминированный и обладает пре- фнксиым свойством. л) Это правила енкогда не испоаьзуется. Оно требуется лля гого. чтобы Р Внл ДМСЬаатамаюм в аормальпое цюрме. гл з теоэия Лвтвамиииэозанного етззоэл в.з.
теогия языков пгостого пеедшествовхния 8.2.15. Покажите, что КС-язык ииеег (1,0)-ОПК-грамматику тогда и только тогда, когда он детерминированный и обладает префиксным свойством. "*8.2.16. Покажите, что каждый детерминированный язык имеет (.Й(1)-грамматику (а) в нормальной форме Хомского, (б) в нормальной форме Грейбах. 8.2.17. Покажите, что если А а к С а — правила типа 4 в канонической грамматике, то А = В, *8.2.!8. Если грамматика С нз алгоритма 8.4 каноническая, то верно лн, что грамматика С„ построенная в этом алгоритме, правопокрываст грамматику С? Что будет в случае, когда С— произвольная грамматика? 8.2.!9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
