Гладкий - Формальные грамматики и языки - 1973 (947381), страница 36
Текст из файла (страница 36)
а) Показать, что классы ОА-языков и ОЬ-языков эффективно замкнуты относительно преобразований, осуществлиемых конечнымн автоматами с выходом. б) Верно ли это для классов линейных, металинейных, итера- ционно.линейных и ОБ-ОАВВ-языкову 5.10. Указать способ построения по диаграмме ОА-грамматикн Г с основным словарем У диаграммы ОА-грамматики, порождающей язык ПрзЕ(Г), 2 ~: — У. 5Л1.
Показать, что класс ОА-языков эффективно замкнут относи- тельно обращения. (Определение см. в сноске нв стр. 156). 5.12. Показать, что классы линейных, металш»ейных, итерацион- но-линейных н ОБ-ОАЕВ-языков эффективно замкнуты относительно пересечения с ОА-языками н относительно подстановки ОА-языков! 533. Множество натуральных чисел Е (или, что то же самое, язык в словаре ([), см. стр.
34) называется периодическим, если существуют такие й, 1, что прн л > й из л ш Е следует и+ !»и ГЕ Показать, что множество ватуральных чисел является цериодическим тогда и только тогда, когда оно есть ОА-язык, при. чем по наименьшим соответствующим й и ! можно построить нужную ОА-грамматику, и обратно, по такой грамматике можно найти наименьшие й и !. 5.!4. а) Указать алгоритм, позволяющий для любой ОА-грамматики (У, йу, 1, )() и любого множества О «е )У» распознать, существует ли такая цепочка х ш У; что О = 0(х) (см.
доказательство теоремы 5.7). б Указать алгоритм, позволяющий для любой ОА-грамматики (У,, 1, Р) н любых цепочек х, у,г «и У* распознать, переводит ли г класс О (х) в класс О (у). 5.15. Будем говорить, что отношение эквивалентности иа У', где У вЂ” словарь, совместимо с кон к а тен виней справ а, если для любых х, у, г ~ю У из х у следует хг уг. Пока. зать, что: а) Если для произвольной ОА-грамматики Г = (У,)У,1, Ю определить отношение — на У' следующим образом: х — у тогда и только тогда, когда П (х) = П(у), где П(и) означает множество тех А ш йт, которые являются концамн путей, начинающихся в 1 и производящих и, то есть эквивалентность, согласованная с Е(Г) и совместимая с конкатенацией справа. б) Для того чтобы язык Е в словаре У был ОА-языком, необходимо и достаточно, чтобы существовала согласованная с Е и совместимая с конкатенапией справа эквивалентность конечного индекса иа У'.
в) Для того чтобы язык Е в словаре У был ОА-языком, необходимо и достаточно, чтобы отношение )1, определяемое следующим образом: х)су = — (»1г щ У*) [хг ш Е =— уг ш Е), имело конечный индекс 5.15. Показать, что следующие линейные языки не являются автоматными; (хй[к»м У+); (хай [х «ш У ) (в обоих случаях мощность У ~ )2); язык примера !2 из 4 1.3. 5.17. а) Доказать следствие иэ теоремы 5.5 непосредственно, т, е. указать способ построения по Б (ОБ)-грамматике Г~ и А (ОА)- гоамматике Гз такой Б (ОБ)-грзмматнки Г, что Е (Г) =1. (Гд П Е (Г») Показать, что если прн этом Г, однозначна, то и Г можно сделать однозначной. б) Показать, что Б-язык (х [х»ж(а, Ь, с, й)+; [х[а [х[э У [х~« — — [к[и) неоднозначен.
5.18. Для тога чтобы каждому дереву вывода в ОБ-грамматике Г отвечало единственное растянутое дерево вывода, необходимо и достаточно, чтобы Г была линейной. Доказать. 5.19. Показать, что для всякой линейной ОЬ-грамматики можно построить эквивалентную ей линейную ОБ-грамматику, все правила 183 УПРАЖНЕНИЯ 182 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ !ГЛ. 3 которой имеют вид А ь аВ, А -ь Ва илн А -ь Л, где А,  — вспомо. гательные символы, а — основной символ. 520. Определим диаграмму линейной ОБ.грамматики Г = = (У, 27,),В) с правилами вида, указанного в упражнении 5.!9, следующим образом (Диковский 1970]: уэламн диаграммы будут элементы 27; если А-ьаВ <ж)г, то из А в В идет дуга, помеченная парОй (а, Л); ЕСЛИ А е Ва Гм )Г, тО ИЗ А В В ИдЕт дуГа, ПОМЕЧЕияая парой (Л, а); 1 — начальный узел; если А-ьЛ щ )7, то А — заключительный узел.
Полный путь определяется так жц как длч диаграммы ОА-грамматики. а) Определить цепочку, производимую путем в диаграмме, так, чтобы множество цепочек, производимых полными путями, совпало с Е(Г). 6) Обобщить понятие диаграммы па случай произвольной линейной ОБ-грамматики.
521. а) Назовем двуленточным конечным автома. т о м (ДК-а в т о м а т о и) машину Тьюринга с двумя лептамн Л, и Ль каждая из которых имеет свою головку, общим для обеих лент алфавитом, инструкциями только типа (!) (стр. 42) и множеством состояний, разбитым на два непересекающихся подмножества 01 и Оз так, что инструкция, имеющая в левой части состояние нз (), (1=1, 2), выполняется на ленте Ль ДК-автомат допускает пару цепочек (х, у), если при записанных на Л~ н Лз цепочках х и у соответственно автомат может, начав вычисление в начальном состоянии с головками, обозревающими левые граничные маркеры, закончить его в заключительном состоянии с головками, обозревающими правые граничные маркеры, Язык, допускаем ы й ДК автоматом М (обозначение: Ь(М)), есть множество допускаемых им пар цепочек.
ДК-автомат М и грамматика Г э к в на ален тн ы, если 6 (Г) = =(хй ~ (х, у) щ Б (М)). Показать, что для всякого ДК-автомата можно построить эквивалентную ему линейную ОБ-грамматику и обратно (ЕозепЬегй 1967]. 6) Пользунсь результатом предыдущего пункта, показать, что подстановка автоматных языков в линейный дает линейный язык. 5.22. а) Показать, что для всякого детерминированного ДК-автомата (упражнение 5.21) можно построить эквивалентную ему одно.
значную линейную ОБ-грамматику. 6) Показать, что язык (хсуу] к а(а, Ь)', у =Л гу угв г)(а, Ь)*), порождаемый однозначной линейной ОБ-грамматикой, не допускается никаким детерминированным ДК-автоматом ]Диковскнй 1970]. 5.23. Показать, что если й зн а*Ь', где а, Ь вЂ” элементарные символы, и К(Е) полулинейно (см. 9 4.3), то ь — линейный язык.
3 а и е ч а и не. Отсюда следует, что всякий ОБ-язык, содержащийся в а*Ь', является линейным. 5.24. Если правая часть хаждого правила НС-грамматики Г содержит не более одного вхождения вспомогательного символа, то для Г можно построить эквивалентную ей лннейвую Б-граыматику, Доказать. 5.25. Указать способ непосредственного построения по данной ОА-грамматике эквивалентной ей симметричной линейной ОБ-трам. маткин. 5.26. Показать, что языки ~а 'Ь ' " ' а АЬ ~ а! —— О, 1, ...) (й = 2, 3, ° ° .) и (л,д, ...х 2 /хп..., хзщ!' )г(У)~2) допускаются чисто стирающими МП-машинами с 23 — 1 поворотами и не допускаются никакими МП-машинами с меньшим числом пово- ротов.
527. Показать, что итерационно-линейный язык (а"Ьч]п = = О, 1, ...)' не является ОБ-ОАЕВ-языком. Указать другие аналогич- ные примеры. 5.28. Показать, что языки (а~+~Ь~ечгг(юЬ~] Ь ! т=О 1 «аь+гйьатЬ+"'] й, 1, т= О, 1, ...), (хууздя] х, у, з ез У', Р (У) ~) 2) допускаются МП-машинами с тремя поворотами, но не допускаются никакими чисто стирающими М!!-машинами.
5.29. Показать, что для каждой чисто стирающей МП-машины М можно построить экнивалентную ей МП-машину 34', в которой для каждого полного вычисления найдется равносильное ему полное вы. численне такое, что рабочая головка на каждом заданном расстоя- нии от начала ленты бывает не более четырех раз. 5.30. Пусть .Уе — класс всевозможных языков, каждый из ко- торых состоит из одной одиобуквеиной цепочки, и прн каждом ! О, 1,... .У!ы есть класс всевозможных языков вида 5 (Ь; аь ..., аз]).п ...
Ез) гле 6 — линейный язык и ).и ..., Та щ гмь.Уе () ... ().Уь Пусть, кроме того, ю!! и 9)! (г' = О, 1,...) озна- чают замыкание У! относительно объединения и умножения, соот- ветственно объединения, умножения и итерации. Показать, что для любого ! = О, 1, ... имеет место .У! — шг; с= 9)! = 2'! +ь 5.3!. Непосредственно (не пользуясь грамматиками) доказать чэффективную эквивалентность» центрально-подстаповочных выра- жений и МП-машин с ограниченным числом поворотов. 5.32. Показать, что всякий ОБ-язык, содержащийся в в! ... вь, г е в, ..., в — фиксированные цепочки, порождается прн й = 1 А ОА-грамматикой и при й - 1 — ОБ-ОАЕВ-грамматикой Г такой, что !з(Г) ( Ь вЂ” 1 (ср. замечания к теореме 4.6 и к упражнению 5.23).
(Языки указанного здесь вида называются о г р а н и ч е н н ы м и; об ограниченных ОБ-языках см. (О1пзЬпгй 1966, гл. Ч].) 5.33. Показать, что: а) Линейный язык Вь ]а 'Ь '...а АЬ А]тыл! 0,1,...; т,-а,У7 ... Ч т„-а,) (3-2,3,...) допускается детермцпированиой чисто стирающей МП-ыапвиной 0 ГЛАВА 6 [34 специАльные клАссы Бесконтекстных языков [гл. а 2 — 1 поворотами и не допускается никакой детерминированной 23 МП-машиной с меньшим числом поворотон. б) Линейный язык Рт 0 Р, 0 ... допускается детерминированной чисто стирающей МП-машиной и не допускается никакой детерминированной МП-машиной с ограниченным числом поворотов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
