Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 25
Текст из файла (страница 25)
Затем определите Е=(ш,.)ж,(Е(6;)) и покажите, что язык Е рекурсивный, но не контекстно-зависимый. ""2.1.25. Покажите, что язык определяетси грамматикой тогда и только тогда, когда он распознается машиной Тьюринга (машина Тьюринга определена в упражнениях равд. 0.4). 2.1.20. Определите недетерминированный распознаватель, памятью которого является первоначально пустая лента машины Тьюринга, причем ее длина не должна становиться больше длины входной цепочки. Покажите, что язык определяется таким распознавателем тогда и только тогда„ когда он контекстио-зависимый.
Этот распознаватель называется линейно ограниченным автоматом (сокращенио ЛО-автоматом). Определение. Индексная грамматика — зто пятерка 6 =- = (Я, г., А, Р, Я), где 1Ч, т н Л вЂ” конечные множества нетерминалсв, терминалов и посредников соответственно, Яс(Ч вЂ” начальный символ, Р— конечное множество правил вида А — Х,Чг,Х,Чг, ...
Х,Ч"„(п) 0) А1" — Х„Ч",Х,Ч', ... Х„Ч'„(и» 0) где АЕ)Ч, Х;Е1Ч()г., )ЕЛ и Ч',~А*, причем, если Хейг, то Ч';=е. Пусть сл и р — цепочки из множества (ХЛ' Ол')*, А Е)Ч, ОбЛ*, и пусть А — Х,Ч', ... Х„Ч'„принадлежит Р. Тогда мы пишем иА0~1=Ф иХ,Ч~,О,'Х Ч' 0' ... Х Ч"„О„'(1 где О;=О, если Х;~1ч, н О;=е, если Х,бл.. Таким образом„ цепочка посредников, следующая за нетерминалом в левой части правила, распределяется по нетермииалам правой части, но ие по терминалам, за которымн никогда не могут идти по* средники.
Если А) — Х,Ч', ... Х„Ч'„принадлежит Р, то иА(0й =!>о аХ1Чг,О; ... Х„Ч'„О„'(1 где О; определяются так же, как и выше. Этот шаг „поглощает" посредника, следующего за А, а в остальном он такой же, как и шаг первого типа. Пусть =Я обозначает рефлексивное н траизитивное замыкание отношения ~в, и пусть, наконец, Е (6) = (Ф! ес б Х* и Я =.',>а и) Пример 2.7. Пусть б = ((Я„Т, А, В, С), (а, Ь, с), ((, а), Р, Я), где Р состоит из правил В- Тй т Т) Т- АВС А(- аА Вг — ЬВ С)- сС Ад- а Вд — Ь Сд — с Тогда Е(б)=(а"Ь"с")а%1). Например, цепочка ааЬЬсс имеет вывод В=ЭТО =~ Т)й =~ А)ав)дС)д =!> аАдВ)дб~д =!РааВ(ЯС)й =:;> ааЬВдб~д ~ ааЬЬС)д =~ааЬЬсбд ~ ааЬЬсс П *2.1.27. Постройте индексные грамматики для языков (а) (ихв ) ш ~ (а, Ь) "), (б) (а"Ь" )п~~1). **2.1.28. Покажите, что каждый индексный язык контекстнозависимый.
2.1.29. Покажите, что каждый КС-язык индексный. 2.1.30. Давайте постулируем распознаватель, память которого представляет собой одно целое неотрицательное число (записанное, если хотите, в двоичной форме). Предположим, что управляющими цепочками, описанными в равд.
2.1.4, являются !21 гл, з элементы теории языков только Х н )'. Какие из следующих функций могут быть функциямн доступа к памяти для этого распознавателя? ( О, если !' четко, ( 1, если ! нечетко. ) а, если ! четно, ( [з, если ! нечетно. ) О, если г четно и под входной головкой (н) )(!) = находится входной символ а, 1 в противном случае. 2.1.31. Какие нз следующих функций могут быть функпиями преобразования памяти для распознавателя нз упр.
2.1.30? (а) д(), Х)=О, а (!', )') = Е+ 1. (б) а(л, Х) — --О, ) Е1, если предыдущая управляющая а (! )") = цепочка была Х, !'+2, если предыдущая управляющая цепочка была )'. Определение. ТАГ-система состоит нз двух конечных алфавитов К н Х н конечного множества правил вида (а, ))), где а, ~Е([к[О л)з. Если у — произвольная цепочка из (?[!)л)з н (а, [!) — правило, то мы пишем ау! -76, т. е. префикса в начале любой цепочки можно стереть при условии, что потом в конце цепочки будет приписано [). Пусть! — * — рефлексинное н трапзитннное замыкание отношения [ —. Для любой цепочки у Е (Х [) 2)" обозначим через /.
язык (гв)шЕЕз н у) — *ш)л). "*2.1.32. Покажите, что Е всегда можно определить некоторой грамматикой. Указание: Используйте упр. 2.1.25 или посмотрите Рйннский, )967). ""2.1.33. Покажите, что для любой грамматики 6 язык ?. (6) можно определить ТАГ-системой описанным выше способом. См. указание к упр. 2.1.32. Откратае проблема 2.1.34. Является ли дополнение любого контекстно-зависимого языка контекстно-зависимым? ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ Если распознаватель из упр.
2.1.26 детерминированный, то он называется детерлтнированным линейно ограниченным (ДЛО) автоматом. 2.1,33, Распознается лн любой КЗ-язык ДЛО-автоматом? 2.1.36. Распознается ли любой индексный язык ДЛО-автоматом? Из упр. 2,!.26 следует, что утвердительный ответ в упр. 2.1.35 влечет утвердительный ответ в упр. 2.1.36. Замечания по литературе Теория формзльньлх языков была в значительной степени стимулирована Х' аботзми Хамского в конце !950-х годов [Хомский, )956, )957, !959з, !959б). орошнмн прнмерзмн ранних работ по порождающим системам служат [Хомский, !963) и [Бзр-Хнллел, !964). Иерархия Хамского грамматик и языков хорошо изучена.
Многие из основных результатов, касающихся иерархии Хамского, приведены в упражнениях. Большинство нз ннх доказаны в книгах Хопкрофта и Ульмана 1)969) н С, Гннзбурпл [!9661. С тех цор кзк Хомский ввел грамматики составляющих, в литературе появнлнсь многие другяе модели грамматик.
В некоторых нз пнх используются спсцязльные виды врапнл. В качестве примеров таких грамматик назовем индексные грамматики !Ахо, )9681, макрогрзмматнкн [Фншер, )966) н грамматики с рассеянным контекстом [Грейбах и Хопкрофт, )969). В других грамматических моделях излагаются ограничения нз порядок применения прзпнл, нзпрнмер в программных грамматнках [Розенкранц, )968! '). Распознаватели для языков тоже нзучзлнсь очень широко. Машины Тьюринга были введены А.
Тьюрннгом в !936 г. Пескоаько позже в работе Мзк-Кзллокз н Питтса [!943! появилось понятие конечного автомата. г!зуче. ине распознавателей было стимулировано работами Мура [)956), Рабина н Скотта [)959) з). В теории языков значительные усилия были приложены для выяснения алгебрзическвх свойств классов языков н для получения результатов, связанных с проблемой разрешимости для разных классов грамматик н рзспознзвзтслей, л!ля каждого нз четырех классов грзллмзтнк з нзрзрхнн Хамского существует класс распознавателей, определяющий в точности зе языки, которые порождаются грамматиками этого класса.
Этн наблюдения привели к изучению абстрактных семейств языков и распознавателей, причем классы языков опредслнются в терминах их алгебраических свойств. Определенные алгебраические свойства клааса нзыков оказываются необходимыми и достаточными для существования соответствующего класса распознавателей для этих языков. Работа з этой области была начата Гинзбургом н Грейбзх [)9691 н Хопкрофтом н Ульмзном [!967). Хороший обзор теории языков к )970 г, дзн Буком [)970 .
ейнс [!970) утверждзег, что левоконтскстные грамматики нз упр. 2.!.6 порождают в точйостн контекстно-зависимые языки '). Упр. 2.!.28 взято нз [Ахо, )968[. ') То, чзо здесь определено, обычно называют канаиигеской сиспммои Поста [з иормильной форме), ТАГ-системз должнз удовлетворять еще неко. торым дополнительным условиям [см. [Минский, Г967)),— Прим. перез. 122 ') А также в ьштричных грзммзтнках Абрахама [)965).— Прим. перез.
з) Следовало бы упомянуть здесь н работу Кляни [)956).— Прим. перез. з) Доказательство этого утверждения см. в 4 3.5 книги Гладкого 1)973).— Прим. перев, !23 ГЛ. З, ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ З.В РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ ИПОРОЖДЕНИЕ 2.2. РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ Регулярные множества образуют класс языков, занимающий центральное положение по отношению к значительной части теории языков. В этом разделе мы опишем несколько методов задания языков, каждый из которых определяет в точности регулярные множества. Среди них — регулярные выражения, праволинейиые грамматики, детерминированные и недетерминированиые конечные автоматы.
2.2Л. Регулярные множества н регулярные выражения Определение. Пусть Х вЂ” конечный алфавит. Регулярное мнолсество в алфавите Х определяется рекурсивно следующим образом: (1) Я (пустое множество) — регулярное множество в алфавите г; (2) (е) — регулярное множество в алфавите 2; (3) (а) — регулярное множество в алфавите В для каждого аЕВ; (4) если Р и 1г — регулярные множества в алфавите В, то таковы же и множества (а) РцЯ, (б) РО„ (в) Р*; (5) ничто другое не является регулярным множеством в алфавите З.
Итак, множество в алфавите В регулярно тогда и только тогда, когда оно либо йу, либо (е), либо (а) для некоторого ай У, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и ите- рации. Определим теперь удобный способ обозначения регулярных множеств в конечном алфавите 2. Определение.
Регулярные выралсенил в алфавите З и регуляр- ные множества, которые они обозначают, определяются рекур- сивно следующим образом: (1) Я вЂ” регулярное выражение, обозначающее регулярное множество Й1, (2) е — регулярное выражение, обозначающее регулярное множество (е), (3) если аЕА, то а — регулярное выражение, обозначающее регулярное множество (а), 124 (4) если р и д — регулярные выражения, обозначающие регулярные множества Р и О соответственно, то (а) (р+ у) — регулярное выражение, обозначающее Р 0 О; (б) (рд) — регулярное выражение, обозначающее Рсг; (в) (р)* — регулярное выражение, обозначающее Р*; (5) ничто другое не является регулярным выражением. Мы будем пользоваться записью р+ для сокращенного обозначения выражения рр* и, кроме того, будем устранять из регулярных выражений лишние скобки там, где это не может привести к недоразумениям.
В этой связи предполагается, что наивысшим приоритетом обладает операция *, затем идет конкатенация и далее операция -1-. Так, 0+10* означает (О+(1(0*))). Пример 2.8. Вот несколько примеров регулярных выражений и обозначаемых ими множеств: (1) 01 обозначает (01). (2) 0* обозначает (0)*. (3) (О+1)* Обозначает. (О, 1)*. (4) (О-,'-1)*01! обозначает множество всех цепочек, составленных из нулей и единиц и оканчивающихся цепочкой 011. (5) (а+Ь) (а-1-Ь+О+1)* обозначает множество всех цепочек из (О, 1, а, Ь)', начинающихся с а или Ь.
(6) (00+11)' ((01+ РО) (00+11)*(01+10) (00+11)*)* обозна. чает множество всех цепочек нулей и единиц, содержащих четное число нулей и четное число единиц. С) Совершенно ясно„что для каждого регулярного множества можно найти по крайней' мере одно регулярное Выражение, обозначающее это множество. И обратно, для каждого рсгулярного выражения можно построить регулярное множество, обоаначаемое этим выражением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
