Гладкий - Формальные грамматики и языки - 1973 (947381), страница 30
Текст из файла (страница 30)
Чтобы в этом убедиться, докажем следующую лемму. Л е м м а 4.15. Пусть М вЂ” детерминированная МП- машина такая, что !.(М) — (Л) не является А«языком. Тогда найдется цепочка ге ~ !.(М), представимое в виде ш = г~у,хуггг так, что (а) уз Ф Л, уг ~' Л; (6) какова бы ни была цепочка и такая, сто о = нзиси !.(М), цепочка о„= х,у",ху"г,и также принадлежит г (М).
Доказательство. Пусть сначала тв и а — произвольные непустые цепочки такие, что ш, щи ен т'.(М). Ввиду детерминированности машины ши-вычисление, оборванное после чтения последнего символа из ш, будет совпадать с гс-вычислением, оборванным после чтения того же символа. При «скобочпой» интерпретации вычисления (стр. 141) это означает, что во всяком случае, внутри сс при допускании цепочки тви будут поставлены в точности те же скобки — и с теми же метками, — что и при допускании и *). Построим теперь по машине М Б-грамматику Г с помощью процедур лемм 4.13, а), 4.14 и 4.12, б). Если ф— система составляющих цепочки х, принадлежащая Т.с(М), и С„' — соответствующая система составляющих из Т.с(Г), то по предыдущему всякая составляющая из С, расположенная целиком внутри ш, принадлежит и системе С „и имеет в ней в точности те же метки; по замечанию 3) на стр.
150 это верно и для систем С'„и С',. В силу следствия из теоремы 7.6*«) грамматика Г имеет неограниченную степень самовставления, и во всяком случае найдется такая цепочка гв ~ т.(Г) = = 7.(М), что Хг (ла) = 3,— иначе говоря, ш представима в виде е,аАГугеггг, где еь еь Гь (г чь Л и отрезки *) Скобки, поставленные ири дону«клики девочки ш нз ее ирзвом конде, могут при доиускзнии ши окзззтьси вчутри и. ") Ознакомившись с докззвтельством этой теоремы, читатель убедитсн, что от настоншей леммы оно не зависит.
152 в-ГРАммАТИКИ И МАШинЫ С МАГАэИННОН ПАмятью !Гл. э УИРА?КНЕНИЯ г, (эг)э, эг)гг)эээ принадлежат С и «происходят» от узлов с одинаковыми метками. По предыдущему отрезки г и гэг(э должны принадлежать и С „и происходить в дереве вывода цепочки гпи от узлов с одинаковыми метками, какова бы ни была цепочка и такая, что шиаз ен Е(М). Поэтому (ср. доказательство теоремы 4.5) для любого и имеем г!3,(",г(э"лэг и ~ Е [М). С помощью леммы 4.!блегкодоказать, что язык примера 2 на стр. 137 — 138 при и ~ 1 не допускается никакой детерминированной МП-машиной. Действительно, в противном случае для некоторой ш ен [аь ..., а„)' можно было бы цепочку гпФ представить в виде гпгй =г,у,ху,гэ так, чтобы было у, чь Л, у, Ф Л и для любой цепочки и е=-[а„..., а„)' имело бы место г,у",ху,"г ийн?гй ее Е. Но если положить и=а[» !+!» ', где а, отличен от последнего символа цепочки ш, то в цепочке г,уэхуэг иагагй на расстоянии 21гь(+(у,1+(у,( от левого и правого концов будут стоять разные символы.
[Стоит заметить, что «очень похожий» язык [хйх(х ен [аь ..., аа)*) допускается детерминированной МП-машиной, — например, с программой [д~ ЧР - уэ! г)эаг г(г+з! аэЬ уз, 'у!+э АЩэ'. уэа! 0?ьячз! г)э 4ф — «уэ,' А1?)ч и+э -+ дз) (уз — единственное заключительное состояние). Символ Ь служит здесь сигналом к изменению направления движения рабочей головки, тогда как в предыдущем примере менять направление приходилось наугад, и поэта!ну в любой момент нужно было иметь возможность это сделать.) Дальнейшие примеры см. в упражнении 4.34.
"Ъ. Уп раж цен ия 4Л. а) Покэзаэь, что для всякой Б-грамматики Г можно по. строить эквивалентную ей Б.грамматику Г', каждое праиило которой либо имеет вид 1-«а, где ! — начальный символ и а — основной символ, либо длина его правой части больше единицы. За и е ч вин е. Очевидно, Т,(и) ~и.
Поэтому Я'Г(Б) = Я'(Б). Тем более Я'(Б) ': — Я'„(НС). б) Показать, что для произвольной Б-грамматики Г функция Тг(и) мажорнруется линейной функцией. 4.2. Показать, что если в теореме 2.2 Г есть Б-грамматика, го и 1 можно сделать Б-грамматикой. 4.3. Оценить изменение временной сложности в конструкции леммы 4.3. 4.4. Показать, что: а) если два вывода в Б-грамматике нме|от одно н то же дерево, то они получаются друг нз друга перестройкой; б) обратное неверно (указать пример).
4.3. Указать пример НС-грамматики, в которой вывод может иметь несколько разных деревьев. 4.6. Поквзать, что для любой Б-грамматики можно построить эквивалентную ей Б-грамматику беэ правил вида А — «В ( — «В (А,В— вспомогательные символы), в которой каждый вспомогательный символ, кроме, быть может, аачального, циклический. 4.7. Указать алгоритмы, позволнющие по любой Б-грамматике Г с данным основным словарем У и любой цепочке х сн У' распознать, выводима лн в Г цепочка: а) содержащая вхождение х; б) начинающаяся с х; в) оканчивающаяся х. (ваг-НН!е) — Рег1еэ — Зйаш)г !96!.1 4.3.
Распространить на ОБ-грамматики леммы 4Л вЂ” 4.10 и теоремы 4.1, 4.2. 4.9. Показать, что языки из упражнений 3.6, 3.13, 3.20, а) не являются бесконтекстными (язык из упражнения 3.6,6) — только при Ь ) 2, язык из упражнения 3.6, г) — только при й .» 1!.
4.10. Показать, что коммутативное замыкание (см. упражнение 3.7) Б-языка может не быть Б-языком. 4.11. Пользуясь теоремой 4.7, показать, что языки (а "Ь "ат 1 т, и = 1, 2, ...; т ~ и) и 1а" Ь"а" 1 т, и = 1, 2, ...; т Ф и) не являются бесконтекстными 4.12. Показать, что нласс ОБ-языков эффективно замкнут относительно операций левого и правого деления на цепочку.
4.13. 1(оказать незамкнутость класса Б-яэыков относительно вычитания и взятия дополнения непосредственно (построив соответствующий пример). 4.14. Проанализировав доказательство леммы 4.3, убедиться, что Б-язык тогдз и только тогда является однозначным, когда он может быть порожден однозначной стандартной бинарной Б-грамматикой.
4.13. Замкнут ли класс однозначных Б-языков относительно объединения, пересечения, усеченной итерации? 4.16. Доказать неоднозначность следующих Б-яэыков: а) (а"ЧРсиг)и(т, и 1, 2, ...Я(а"ЧР»иг(т(т, и 1,2, ...); б) (азэгэси(Ь, т, и 1, 2, ...; и~(Ь Ч и~т); в) (аэээсгэа"'еи(Ь, т, и=!, 2, ...)()(аэбмсмг(иеи(й, т, и 1, 2, ...). 4.17. Замкнут ли класс неоднозначных Б-языков относительно объединения, умножения, усеченной итерации? 155 УПРАЖНЕНИЯ 354 3-ГРАММАТИКИ И МАШИНЫ О МАГАЗИННОЙ ПАМЯТЬЮ 1ГЛ. 4 4.18. а) Показать, что произведение неоднозначного Б-языка и двухэлементного языка может быть однозначным Б-языком б) Верен ли аналогичный факт для одноэлементного языка? 4И9. Построить Б-грамматику, порождающую язык Е а"Ь'суг('е* — Е', где Е' — язык из упражнения 4.16, в) [И!!ап 1966].
[Указание. Представить Е в виде Е~[)Е»[)Е», где Е! =(акйэсгФе [ йг), причем й~ означает Ьчь! 8 д+ !чья+ [, йз означает ! чь [ 8с И+ [ чь ! + 1, йо означает д Ф А а ] Ф !.] с 4 к 4 4.20. Положим Е,, а !а"Ьа 'Ь ... Ьа а 'Ьа Ьа а+'Ь ... Ьа о[а, !! 1. 2 ° ] Е«Е«~()Е«з[) ". [)Е««, Е=Ег(]Е», " (э, 4=2 3...,.; А <к). Показать, что: а) для любого натурального числа к в Е, найдется цепочка, имеющая в любой Б-грамматике, порождающей Еь не менее з раз. личных деревьев вывода; б) для любого натурального числз з в Е найдется цепочка, имеющая в любой Б-грамматике, порождающей Е, ие менее з различных деревьев вывода. 3 а и е ч а н и е.
Языки Е, и Е не только бесконтекстны, но и линейны (см. ниже, $5.2). 4.21. а) Поназать, что при любом л 2, 3, ... язык М» Ц(а Ь)' порождается Б-грамматикой с а+ 1 вспомогательными ! ! символами и не порождается никакой Б-грамматнкой с меньшим числом вспомогательных символов. 3 а и е ч а н и е. Легко видеть, что все языки.М автоматные. б) Указать пример й-языка, порождаемого Б-грамматикой с двумя вспомогательными снмволамн и не порождаемого никакой Б.грамматикой с одним вспомогательным свмволом. [Сгпзйа 1967]. 4.22.
Построить МП-машины, допускающие языки примеров 6, 7, 9, б) из 3 1.3 и языки из упражнения 1.!5. 4.23. Построить деревья вычислений цепочки а"Ь' в машине примеРа 1 из $4.5 и цепочки а!азазазаза, в машине пРимеРа 2 из й 4.5. 3 2 4.24. Показать, что лля машины примера 3 из 6 4.5 ширина деревьев вычисления не ограничена.
4.25. Дополним МП-машину М третьей лентой — назовем ее выходной — со своей головкой и своим елфавитои н добавим к ее программе инструкции аида да-»дйа, где а — выхй»хной символ; вы. полнение такой инструкции будем интерпретировать как запись сим. вола а. Полученное устройство М' назовем МП- ма ш иной с в их о д о м. Если М' сможет, начав работу, когда М находится в начальной х-ситуации и выходная лента густа. закончить ее, когда М находится в заключительной х-ситуации и на выходной ленте записана цепочка у, то мы снажем, что М' п е р е в о д и т х в у, и будем писать у = М'(х).
Положим: М'(Е) (у[Вх[х щЕ6 у М'(х)]) (Е з- У ); Ео(М) = М (У ). Показать, что: а) для любой МП-машины М мгжно построить такую МП-ма. шину с выходом М', что Ео(М') Е(М)! б) для любой МП-машины с выходом М' можно построить такуго МП-машину М, что Е(М) = Ео(М'); в) для любой Э-машины М можно построить такую Б-гЕоамматику Г и такую МП-машину с выходом Мь что М~(Е(Г)) = (М). 4.26. Показать, что для любой МП.машины можно построить эквивалентную ей нормальную МП-машину, у которой в любом дереве вычисления непустой цепочки все висячие узлы помечены входыми символами (так что в скобочном изображении соответствующей системы составляющих — см. стр.
141 — не будет «пустых» пар с обок). Доказать это двумя способами: с помощью теоремы 4.3 (и анализа доказательств лемм 4.12 — 4.14) и непосредственно (без обращения к грамматиком). 4.27. Доказать теорему 4.8,а) и результат упражнения 4.12 с помощью МП.машин (т.- е. указать способ построения по МП-машинам М, и М, МП-машины, допускающей язык Е(М~) (] !.(М,), 4.28. Указать алгоритм, позволяющий для произвольной МП-машины М распознать, ограничена ли ширина множества Ес(М), и в случае положительного ответа найти ее верхнюю границу.
4.29. а) Найти для цепочки ааЬЬаЬ еще одно дерево вычисления в машине примера 3 из 5 4.5, кроме изображенного на рнс. 6. б) Убедиться, что для любого натурального а найдетси допуснаемая этой машиной цепочка, имеющая больше а вычислений. 4.30. Показать, что язык (а Ь "а" Ь [ т, и = О, 1, ...) не допускается никакой МП.машиной, рабочий алфавит которой состоит из одного снмвола.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
