Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 44
Текст из файла (страница 44)
Состояния вида [д, !] указывают, что в данный момент 2!6 Р перешел в заключительное состояние. Состояния вида [!), 2] используются только для обозначения закл!Очителып>!х состояний. Если Р' находится в состоянии [д, О] и в соответствующий момент моделируемый распознаватель Р собирается сделать ие е-такт, то Р' сначала переходит в состояние [д, 2], а затем моделирует Р. Таким Образам, Р' допускает тогда и только тогда, когда Р не допускает. Тот факт, что ДМП-автомат Р— дочитывающий, гарантирует, что и у Р' всегда есть шанс допустить входную цепочку, если Р не допускает ее.
Формальное определение функции 6 такавсс (1) если а й (г, и ~ Х и 7 б Г, то 6' ([д, ! ], и, 7) =- 6' ([д, 2], и, 2) = ([р, 2], Т) где 6 (д, а, 7) = (р, у), ! = О, если р !ЬР, и ! =1, если р Е Р1 (й) если д Е (), 7 б Г и 6 (д, е, 7) ='(р, Т), то 6'([д, !], е, Я) =([р, 1], Т) 6'([д, О], е, 7)=([р, !'], Т) где ! =О, если р (Р, и ! = 1, если р ~ Р; (й!) если 6(т), е, Я) = Я, то 6'([д, О], е, 7) =([с), 2], 7).
Правило (!) Относится к не е-тактам. Вторая компонента состояния правильно принимает значение 0 или 1. Правило (й) относится к е-тактам, и здесь опо управляется со второй компонентой состояния, как задумано. Правило (й!) позволяет Р' допускать входную цепочку в точности тогда, когда Р не допускает ее. Формальное доказательство того, что Ь (Р')=7.(Р), мы опускаем. С) Детерминированные КС-языки обладают и другими важными свойствами, Мы рассмотрим их в упражнениях и в следующем разделе.
УПРАЖНЕНИЯ 2.5.1. Постройте МП-автоматы, допускающие дополнения (относительна (а, Ь)') следующих языкощ (а) (а" Ь "а" '! и, ~ 1), (б) (в!Рн ! т ~ (и, ЬТ! *), (в) (а~Ь'и"Ь" (и, и ~ !), (г) (и!!о/в~ [и, Ь)*). Указание: Пусть недетерминированный МП-автомат делает пред- положение относительно того, почему ега входная цепочка не принадлежит данному языку, и проверяет, верно ли это пред- положение. ГЛ. 2. ЭЧНМЕНТЫ ТЕОРИИ ЯЗЫКОВ УПРАЖНЕНИЯ 2.5.2. Докажите, что МП-автомат из примера 2,3! допускает язык (пчел ! в Е (а, Ь) *) . 2,5.3. Покажите, что каждый КС-язык допускается МП-автоматом, который за один такт увеличивает длину магазина не более чем па единицу.
2.5.4. Покажиге, что каждый КС-язык допускается таким МП-автоматом, что если (р, у) б 6 (а, а„Х), то либо 7 =е, либо 7=-2, либо 7=--Г2 для некоторого Г 6Г. Указание: Рассмотрите конструкцию леммы 2.21. 2.5.5. Докажите, что каждый КС-язык допускается МП-автоматом, не делающим е-тактов. Указание: Вспомните, что каждый КС-язык порождается грамматикой в нормальной форме Грейбах. 2.5.6. Покажите, что для каждого КС-языка Е найдется такой МП-автомат Р с двумя состояниями, что Š—.Е(Р). 2.5.7.
Дополните доказательство леммы 2.23. 2.5.8. Найдите восходящие и нисходящие распознаватели (МП-автоматы) для следующих грамматик: (а) 5- а5Ь!е (б) 5 А5)Ь А — 5А )а (в) 5 — 55~А А ОА1)5(01 2.5,9. Найдите грамматику, порождающую Е,(Р), где ° =((7„7„02), (а, Ь), (Л,, А), 6, а„, 2„, >д,)) и 6 задается равенствами 6(р„а, 2,) =-(д„Аг„) 6(д„, а, А) =-(йо АА) 6(ао а, А)=-(д„, АА) 6(рн е, А)=(а„А) 6(42, Ь, А) =(а„е) Указание: Для бесполезных нетермипалов строить правила не обязательно.
"2.5.10. Покажите, что если Р.— (1Е, Х, Г, 6, д„, 2„Р) —. МП-автомат, то множество цепочек, которые могут появиться в его магазине, регулярно. Иначе говоря, покажите, что множество (а)(9„, в, Л,)'„— *(д, х, а) для некоторых д, в и х) регулярно. 2.5.11.
Дополните доказательство леммы 2.26. 2.5.12. Пусть Р— МП-автомат, для ноторого существует та- кая константа й, что в его магазине всегда не более'й символов. Покажите, что Е(Р) — регулярное множество. 2.5.13. Постройте ДМП-автоматы, допускающие следующие языки: (а) (О'17(1» ~), (б) (в)в состоит из равного числа символов а и Ь), (в) Е(6,), где 6„— обычная грамматика, определяющая про- стые арифметические выражения. 2,5,14. Покажите, что ДМП-автомат из примера 2.36 допу- скает язык (вета" ~в 6 (а, Ь)').
2.5.15. Покажите, что если конструкцию леммы 2.21 приме- нить к расширенному ДМП-автомату, то получится ДМП-автомат. 2.5.16. Докажите, что Р н Р' в лемме 2.27 допускают один и тот же язык. 2.5.17. Докажите, что шаг (2) алгоритма 2,16 действительно отличает С, от С, 2.5.18.
Дополните доказательство теоремы 2.23. 2.5.19. Определенные нами МП-автоматы делают такт неза- висимо от входа только тогда, когда при этом не сдвигается входная головка, Можно ослабить это ограничение и позволить обозреваемому входному символу влиять на то, что делается в данном такте, и тогда, когда входная головка остается не- подвижной. Покажите, что при таком расширении класса МП- автоматов они все еще допускают только КС-языки. *2.5,20.
Можно еще более расширить класс МП-автоматов, позволив входной головке двигаться по ленте в обе стороны и снабдив входную ленту концевыми маркерами. Назовем такой автомат 2МП-автоматом (двусторонним МП-автоматом), а если ои детерминированный, то 2ДМП-автоматом. Покажите, что сле- дующие языки распознаются 2ДМП-автоматами: (а) (а»Ь»е» ( и ~ 1), (б) (вв)в~(а, Ь)»), (в) (а'»)и ~ 1). 2.5.21. Покажите, что 2МП-автомат может распознать язык (вхв(в, хС (О, 1)"). Открытые проб.2емы 2.5.22. Существует ли язык, который допускается 2МП-ав- томатом, но не допускается 2ДМП-автоматому ГЛ, 2. ЗЛЕМЕИТЫ ТЕОРИИ ЯЗЫКОВ 2.5.23, Существует ли КС-язык, который не допускается 2ДМП-автоматом? 'г'пражнрния ни программирование 2,5.24. Напишите программу, моделирующую детерминированный МП-автомат. "2.5.25.
Придумайте язык програмМИраваНИЯ, прИГОднЫй для задания МП-автоматов. Постройте компилятордля Вашего языка. Исходная программа в этом языке должна определять МП-автомат Р. Объектная программа должна описывать распознаватель, разумным способом моделирующий поведение Р иа входных цепочках иг. 2.5.26. Напишите программу, которая в качестве входа воспринимает КС-грамматику и строит для нее недетерминированиый нисходящий (или восходящий) распознаватель. Замечания по литературе Взжггость магазииов [известиых также под названием стеков) в процессах обработки языков была осозиаиа в иачале 1960-х годов. Эгтиигер [1961] и Шготцеиберже [!963] первыми формализовали понятие автомата с магазиииоа памятью. Эквивалептиость МП-автоматов и КО-грамматик была показаиа Хомским [19621 и Ээи [19631.
Двусторонние МП-автоматы изучались Хартмаиисом и др. [1966], Грэем и др. [19671, Ахо и др. [1966], Куком [19711. 2.6. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ В этом разделе мы исследуем некоторые из основных свойств КС-языков. Упоминаемые здесь результаты иа самом деле образуют малую долю огромного богатства знаний О КС-языках. В частности, мы рассмотрим некоторые операции, относительно которых замкнут класс КС-языков, некоторые результаты о разрешимости и кое-что о неоднозначных КС-грамматиках и языках.
2.6А. Лемма Огдена Начнем с доказательства одной теоремы (леммы Огдена) о КС-грамматиках, из которой можно будет извлечь ряд результатов о КС-языках и, в частности, „лемму о разрастании" для КС-языков, Определение. Позицией в цепочке длины й назовем такое целое число г, что 1 =.='г <[г. Будем говорить, что символ а занимает позицию г (или г'-ю позицию) в цепочке иг, если иг=-гигаигз н ~иг, [=г' — !. Например, символ а занимает третью позицию в цепочке Ьаасс.
з,а. сВОйстВА контекстно.сВОВОдных языкОВ Теорема 2.24. Для каждой КС.грамматики 6=(]л[, Х, Р, 3) существует такое целое число ге хм[, что если гЕ7.(6), [г!)[г и в цепочке г вьгделены й или более Различных позиций, то г можно записать в ваде игквх[г, причем (1) иг содержит котя бы одну выделенную позицию; (2) либо и и о обе содержит выделенные позиции, либо х и у обе содержат выделе~ныл позиции; (3) гхсх содержит не более й выделенных иозлций; (4) существует такой нетерминал А„что О =>с иАУ~гипАхУ ~~; ... -?ОисгАхгУ=Э+~моги!к'У для всех г~ О (в случае г'=О вывод имеет вид 3 =>аеиАу=эаеиигу).
Д о к а з а т е л ь с т в о. Пусть т = 49Н н 1 — длина самой длинной из правых частей правил множества Р, Выберем й =-Л"+' и рассмотрим дерево вывода Т некоторой цепочки гЕЦ6), где (г~' й. Пусть в цепочке г выделены по крайней мере [г позиции. Заметим, что Т должно содержать хотя бы один путь длины, не меньшей 2т+3. Выделим листья дерева Т, которые в кроне г дерева Т занимают выделенные позиции. Назовем вершину и дерева Т ветвящейся, если среди ее прямых потомков есть хотя бы два, скажем п, и п„таких, что среди потомков каждого нз них есть выделенные листья. Построим путь и„, и„... в дереве Т следующим образом: (1) пг — корень дерева Т; (2) если мы нашли п; и только один прямой потомок этой вершины имеет выделеннйе листья среди своих потомков (т.
е. И! — НЕВЕтВЯЩаЯСЯ ВЕРгиниа), тО ВОЗЬМЕМ В КаЧЕСтВЕ Пггт ЭТОГО прямого потомка; (3) если ггг — ветвящаяся вершина, то выберем в качестве и;, того прямого потомка вершины и„который имеет среди своих потомков наибольшее число выделенных листьев (если таких прямых потомков несколько, выберем самый правый, но можно взять н любой); (4) если и; — лист, то путь окончен. Пусть и„и„..., ир — путь, построенный описанным способом. Простои нндукцией ~о 1 можно показать, что если среди вершин п„..., и; есть г ветвящихся, топ;„имеет по крайней мере Л"" выделенных потомков. Базис, 1= О, тривиален: г=.-О и и, имеет по крайней мере й =Р "выделенных потомков. Для доказательства шага индукции залгетим, что если иг — пе- ВЕтВЯЩаЯСЯ ВЕРШИНа, тО П, И Поьг ИМЕЮТ ОДНО И тО жЕ ЧИСЛО выделенных потомков, и что если гг,— ветвящаяся вершина, то пг т имеет по крайней мере (]Д)-ю часть выделенных потомков вершины пг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
