Гладкий - Формальные грамматики и языки - 1973 (947381), страница 15
Текст из файла (страница 15)
«Нулевой шаг» построения состоит в следующем. Если существует грамматика Г, и Р(Ге, хс) = 1(!хе~) (что эффективно проверяемо), то полагаем хз ф Ее и й(0) = О. В противном случае (т. е. если грамматики Гз не существует или неравенство Р(Гз, хз) ()(!хз!) не имеет места) полагаем хе ен Ьз, а 6(0) остается не определенным. Пусть произведены шаги с номерами О, ..., л — 1, в результате которых для каждой из цепочек хе, ..., х ! решено, принадлежит лн оиа языку Т.з, и для какнх-то чисел !г, ..., 1, из ряда О, ..., л — 1 найдены значения функции опровержения, причем все эти значения различны; мы будем говорить в этом случае, что «грамматики Г„( , ..., Г„ ) опровергнуты».
Тогда и-й шаг состоит в следующем. Проверяем выполнение неравенств: (0) Р(Г,, х„) = !(!х„!); (1) Р(Гг, х„) =, = !((х„!); ...; (п)Р(Г„,х„) «= !(!х,!) (точнее, тех из них, которые имеют смысл, т. е. для тех ! ( и, для которых Г» существуют). Если гь, гз — все те числа из ряда О, ..., а, для которых соответствующие неравенства справедливы, ищем среди них наименьшее — пусть это 1р,— для которого грамматика Г еще щ не опровергнута.
Если такое число нашлось, полагаем 6(и) = гв, х„ф Лз. Если такого числа нет, а также если ни одно из неравенств (0)...,, (и), имеющих смысл, не выполняется (в частности, если ни одно не имеет смысла), то полагаем х„ен Ьз, а й (х) оставляем не определенным. Рекурсивность построенного языка Ье очевидна, н порождающую его грамматику легко построить по алгоритмам, вычисляющим )(и) и график Р(Г,х). Ясно также, что г'.з не может порождаться ни одной из опровергнутых грамматик (поскольку из Р(Г,х) = !(!х)) следует, во всяком случае, что хе= Е(Г)). Поэтому для завершения доказательства достаточно установить, что всякая грамматика ГА, для которой найдутся сколь угодно большие числа и, удовлетворяющие неравенству Р(Гю г.) ( 1(л), рано или поздно опровергается.
Но имеет место даже более сильное утверждение: грамматика ГА будет опровергнута, если существует й+1 чисел лгь ..., пгз+ь не меньших й и таких, что для каждого 1=1, ., й+1 имеет место Р(Гы (х„,!)(<)(~х,~) Действительно, пусть Г» обладает указанным свойством н никогда не опровергается Тогда на каждом из шагов с номеРами ть ..., гцз.ы Должна быть опРовеРгнУта некоторая грамматика с номером, меньшим й; иначе говоря, функция опровержения для каждого из чисел лгь ..., лгз+! будет определена и примет значение, меньшее й, а это невозможно из-за равнозначности данной функции. Упражнения 2.1. з) Найти временную сложность, левую н прянуло глубину для каждой нз грамматик примеров 6 — 13 нз й 1.3.
б) Нзйтн емкость грамматики примера 13 нз $1.3, в) Найти разброс н активную емкость для кзждой нз грамматик примеров 7, 3, 1О, 11, 13 нз 5 1.3. 2.2. Покзззть, что для любой грамматики Г н любой общере. курснвной Функции 1(т), удовлетворяющей условню чгт(т ~ Пт)1, можно построить грзммзтнку Г', зквнвзленгную Г н такую, что зг (л) =1(5г ( )) 2.3.
Пусть У, — нлзсс всех грамматик, у которых левые части прзннл не содержат основных символов. Пусть далее 'л(~, О, г, !(н, г"г (л), ..., гг (и))), где У вЂ” класс грамматик, Π— з-местнзя операция нзд языками, г — квнзнснгнзлнзнрующнй оператор для грамматик н 1(л, ть ., т,) — общерекурснвнзя функцня, означает: «Для любых грамматик Гь ..., Г, щн можно построить грзммзтнку Г ен», порождающую язык 0(Ь(Г1), ..., ь!Г,)) н геную, что рг(п) ~!(л, Рг (л) рг (н))».
Показать, что н) Прн г" = 7, 5, Фл, ~п, ! имеет место 21(З ! " " щзх(рг,(л), Рг,(л))): 77 УПРАЖНЕНИЯ [ГЛ. 2 СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ б) имеет место ег(У [, Х, Т, шах (Т, (И)+Т. (л — И))), 0<а<и Й(У Р Х Е щ'х (Ег (И) Ег. (и — И), и). 0<в<и 2[(У Р Х 'У~, щах('Мъг,(л) 9ъ(л))) (Ъ=Л, П), 21(У Р Х О шах(ОГ (и), Ог (и), л)) 2[(У и Х ) шах ()г (л), )г (и))+ 1) (Х вЂ” знак УмножениЯ); в) имеет место 2[(~Р й, Т, Тг (л)+Тг (,)+,з), 2[(У [, й, 7, шах()г (л), )г (и))+ и), и — при Р = Е, ""'ул, ф~, .О— Й(У [, й, Р, шах(Рг (л), Рг (и))); г) при О=+, ' имеет место 2[(л [, О, Т, птах [Т, (и,)+ ...
+Т,(иь)))(и )1), 2[(У"[, О, Е, птах (Ег(и — И) + И)), 2[(У [, О, лу~ Фг~(л)) а<З<л (Ъ=Л, П), й (У Р О, О, щах (Ог (л) п) + 1) 5 (У [ О 1 [г (и) + 1). 2А. Вывести соотношения, аналогичные приведенным в упражне- нии 2.3: а) для подстановнн; б) для левого и правого деления на фиксированную цепочку. 2.6. Панаэать, что для Р = Т, 3 все соотношения упражнения 2.3 сохравяют силу при замене класса У ~ классом Г. 2.6.
П усть У"~ означает то же, что в упражнении 2.3, и пусть 1 — функция 7(л) = 1 и С вЂ” класс всех функций-констант, Показать, что: а) Пр„Р з)ул Фхп Ы,' (т,) — ЯР (У-, й НС) = Ы7 (Б) = =.Уся(~[) =.Уси(У., й НС) = оси(Б) л); б) Ы,'(У,) = 2'[, (У-, й НС) = Ы,' (Б) = Ып (У-,); в) Ыс(У [) =.Ус[(У, й НС) = Ысг (Б). * ) При Р = к Ф это класс А-языков, при Р = Π— класс Л П линейных языков (см. ниже, 6 6.3 и следствия из теорем 7.2 и 7.3). Заметим, что для любого класса функций 5 имеет место Я3(У [)- Хъ(Г) Ые (У [йНС)=У6(НС), а если $ замкнут относительно умножения на константу, то Ы.г(т[) = Ыяг (Г) Еяг (У.[й НС) = Ыяг (НС) (см. замечание на стр. 61).
2.7. Пусть У з — класс всех грамматик, у которых левая часть каждого правила содержит хоть одно вхождение вспомогательного символа, и 1, С те же, что в упражнении 2.6. Показать, что: а) при Р='Д~, Фг'" ЫР,(У;) = Ы," (НС) = ЫР, (Б) = 2',Р(К,) = = ~ с (НС) ~ с (Б) ~ ю (У [)' ~1 ~[ (~2) ~С (У 2) ~! (У 2) ~С ~С(У 2) Заметим, что для любого класса функций 5 имеет место Ы'я(9 2)=.Уз (Г], а если 5 замкнут относительно умножения на 3 5 константу, то Е'я (У )=Ыя~(Г) (ср. замечание к упражнению 2.6), 2.8. Показать, чта при Р=гу'"', ФР, О для любой грамматики П Г н любого положительного действительного числа с можно по.
строить грамматику Г', эквивалентную Г и такую, что Р~ (и) < < шах(и, 1, сР(л)). Если прн этом à — НСч сответственно Б-грамматика, то н Г' можно сделать НС (Б)-грамматикой. 2.9. Пусть Р(Г,л) — квазисигнализирующнй оператор для трам. матик, н участвующая в опредеденни Р функция [(Г, О, [) обладает следующим свойством: существует функция й, отображающая (Е 0 Е,)л в натуральный ряд, обращающаяся в нуль на Е* и такая, чта для любой грамматики Г и любого вывода 0 = (ыз, юь ..., ы ) в Г имеет место [(Г, О, [) = д(ы~).
Показать, что в этом случае для любой общерекурсивной функции И(и) и любой грамматики Г = (1', йт, [, )т), для которой И(л) )я(/) и Е(Г) Ф Ы~, суше. ствует бесконечно много чисел л, удовлетворяющих неравенству Рг [л) ~ И(и), 2.10. а) Показать, что если для класса грамматик У существует общерекурсивная функция [(л) такая, что в любой грамматике ГшУ длйны полных выводов цепочек нз Е(Г) длинй, не превосходншей л, не превосходят [[л), то для любого квазисигналнзирующего оператора Е соответствующий относительный оператор Р~ явлнется сигнализирующнм и для любой грамматики ГшУ функция Рг(и) рекурсивна. б) Показать, что если для класса грамматик У существует общерекурсивная функция )(и) такая, что в любой грамматике Г гм У длйны цепочек, встречающихся в полных выводах цепочек иэ Ь(Г) 78 сигнализирующиа Еундцнн (гл, т длинй, не большей л, не превосходят 1(п), то для любого квазисигловню упражне- нализирующего оператора Р, удовлетворяющего условн.
ния 2.9, соответствующий относительный опе а Рх р тор является сиг- налнзирующим и для любой грамматики Г ш У функция Р и е- курсивна. ункция г (и) ре- 2.! 1. д щую множество Всевоз. Построить грамматик, по ож аю епочек из (п, ), являющихся иодами грамматик при спо- собе кодирования, примененном в доказательстве тео емы 2.4. 2.12, Указать способ пост пения 2.4 2.6 теорем, и ., по грамматике Ггп порождающей язык рождающей язык 1. =(н(Г) чу хчу р1Р(Г, х) = р) в словаре , 1, 4ь), де н (Г) и н (х) — коды грамматики Г и цепочки х (см. доказательство теоремы 2.4) и грамматике Г~з, порождающей язык У-з=(п, Ь, 1, 4Р)' — Х(га).
2.13. а) По казать, что при Р=о грамматика Г, из тео емы 2.4 может быть построена так, чтобы им л имело место неравенство с з теоремы ог (и) =гпах(5, (и(п)), йз'(Я1"11, йз'(и(""), где я(л) =2" + )(2")+1, й — константа и 5,(л) = 5, (ГР Г, Гз — грамматики из упражнения 2.12). I гг (з) б) Получить аналогичную оценку длн Т (и), 2.14. На" айти временнйе и емкостные сигнализирующие машин, по. го строенных при выполнении упражнений 1,!6 и 1,17.
2.16. Сфо и лн о ф р у р вать определения временной и емкостной сиг- нализирующих для Н-машин и ОН-машин (упражнение 1.л)). Йайтн соотношения между сигнализирующими Э-м, Н- -машин, -машин и ОЙ- 2.16. Показать, что если функция Тг(л) примитивно рекурсивна, то и язык (. (Г) примитивно рекурсивен.
ГЛАВА 3 ГРАММАТИКИ СОСТАВЛЯЮЩИХ й 3.1. Деревья выводов Пусть Г=()г, ))У, г', )т) — НС-грамматика, Р =(юо, ..., ю„) — вывод в Г такой, что ~ юа ~=1, н Р'— =(ю',, ..., ю„' „ю ), ю',=~зеф,ет),, — некоторый соответствующий Р размеченный вывод. ПУсть юг — — йи ... й,а, (бггеи)Т0 В'). Если ф1-эфг— правило, применяемое на 1-м шаге Р при разметке, отвечающей Р', то фг и зРг можно представить (вообще говоря, не единственным образом — см.
упражнение 3.2) в виДе фг=Х,Агй„фг — )(10гй„гле Агни В" )(т й1еи()г()((У) йг еи((~ 0)(г) ° Фиксировав для каждого 1 1, ..., и — 1 такое представление и обозначаЯ точкУ йи . Рд 1 ~ерг(еуп(чч ° . ()иг цепочки юг через Вп, будем говорить, что точка Вг+ц( цепочки юьь1 является непосредственным потомм ко м точки В,) цепочки юг, и писать ВН-з Вг4~ 1, если либо а) )=)'(~~ $1 1, либо б) 1>) $,)+1, /'= =)+! Вг) — 1, либо, наконец, в)1=1 йг (+1,~ ~~1+1~(1'( (!31!+(0~ ! (т. е. либо Вг+1 1 является «копией» Вн, либо Вп — точка, заменяемая на 1-м шаге, а Вг+ц) принадлежит заменяющему ее отрезку).
Обозначим теперь через М' множество всех точек всех цепочек юо,, ю . Ясно, что граф (М'1 -») является деревом. Для и, р еи М' будем писать а ( б, если либо а) и и б являются точками одной и той же цепочки и и < б, либо б) существуют и', р' я М', удовлетворяющие условию а) и такие, что из иих идут пути в и и в р соответственно. Отношение(есть, очевидно, частичный порядок. Биграф(М', -ь, () мы будем называть рас. тянутым деревом вывода Р, ДЕРЕВЬЯ ВЫВОДОВ ГРАММАТИКИ СОСТАВЛЯЮЩИХ ]гл. з 3 з.н 80 8! Прн графическом изображении растянутого дерева вывода удобно помещать вхождения, принадлежащие одной цепочке, на горизонтальной прямой, и отношение ( понимать как «левее» (ср.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
