Гладкий - Формальные грамматики и языки - 1973 (947381), страница 13
Текст из файла (страница 13)
Ясно, что при «детерминизации» машины время вычисления и число используемых ячеек будут, вообще говоря, расти. Просмотр конструкции, примененной в доказательстве теоремы 1.2, дает возможность оценить этот рост. Именно, пусть хенЕ(М), и при этом то полное х-вычисление С машины М, имитацией которого заканчивается (единственное) полное х-вычисление С~ машины Мь имеет длину 1, а максимальная длина рабочей ленты в вычислении С равна ж Соответствующие величины для вычисления С~ обозначим Г, и зь На каждом «макрошаге» вычисления С, имитируется некоторое х-вычисление машины М, длина которого 1' не превосходит 1; поэтому длина участка рабочей ленты между Ы и началом 2 на данном макрошаге никогда не будет больше 1 (в начале макрошага она равна О и на каждом «М-шаге» может возрасти разве что на 1), а длина 2 в точности равна Р.
Отсюда ]гл:3' ' СИГНАЛИЗНРУКЗЩИЕ ЕУНКЦИИ $ 2.3] ускОРение и сжАтие Въ]еодОе э! (]х]+ 21+ 3. Далее, каждый макрошаг состоит из 1' «М-шагов», каждый из которых требует не более 2(]х]+2У+3+ Р) элементарных шагов машины М! (Р— постоянная; при выполнении «М-шага» головка должна «прогуляться» из начала цепочки длины не бо- лее ]х]+ 2Р+ 3 в ее конец и обратно, выполнив «по дороге» ограниченное число Специальных операций— собственно «М-шаг», перенос метки и т. п.); после вы- полнения последнего «М-шага» для завершения макро- шага может понадобиться еще не более ]х]+ 2У+ 3+ + Р, элементарных шагов (Р! — постоянная). Всех ма- крошагов будет не больше, чем различных цепочек в ! ]+! алфавите Р длины, не превосходящей 1, т. е. наконец, до начала первого макрошага машина должна сделать 2(]х1+4) шагов. Это дает 1! ( Ай!+ей(В]1+ + Вз]х]+ Вз), где А, В], Вм Вз — постоянные.
Отсюда непосредственно следует Л ем ма 2.3. Для любой Э-машины М можно по- строить ДЭ-машину М], допускающую язык 1(М) и такую, что Тм,(п) (» Ай м ]+ Тм (п) (В]Тм(п) + Взп+ Вз), 5м,(п) (2Тм(п)+ а+ 3, гдг й — число инструкций машины М и А, В], Вз, Вз— постоянные, зависящие от М. й 2.3. Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин В построениях этого параграфа важную роль будет играть «лемма о сцеплении», которую мы сейчас сформулируем и докажем, введя предварительно! понятие сцепленной грамматики. Грамматика называется с ц е п л е н н о й, если в каждом ее размеченном полном выводе каждый следующий шаг зацеплен с предыдущим.
Л ем м а 2.4 (о сцеплении). Для произвольной грамматики Г можно построить эквивалентную гй сцепленную грамматику Г' такую, что 5г (и) =5г(п) Тг (п) (яТг(п), гдг й — постоянная, зависящая ог Г (и допускающая эффективное вычисление), Д о к а з а т е л ь с т в о. Пусть Г = (У, Ю, 1, В). В силу леммы 2.2 мы можем считать, что левые части правил Г не пусты, и рассматривать только такие выводы в Г, в которых правило с пустой правой частью применяется разве что на последнем шаге.
Сопоставим каждому символу а ен У () )У взаимно однозначным образом двух «двойнико⻠— новые символы а и а'] мното жества «двойников» обозначим соответственно 2 н Я. Каждому правилу Р РР- У!" У«ЕЕ В Ф! У]~У0~') сопоставим множество, состоящее из всевозможных правил вида йз ЕРО ГЕ РЕО РЯΠ—, О „О (правила 1-го рода). Каждой паре а, р ен У () 'е! сопоставим правило а(]о- аоб (правило 2-го рода), каждому а ен У вЂ” правило а- а (правило 3-го рода), каждой паре а, Ь ~ У вЂ” правило аоЬ- аЬ (правнло 4-го рода). Положим Г' = (У, 2()Яо, Т,В'), где Я' — совокупность всех правил 1-го — 4-го рода.
Сцепленность Г' легко проверяется непосредственно. Докажем эквивалентность Г и Г'. Для каждого упорядочиваемого вывода Р = (о]о, ..., о] ) в Г легко построить вывод в Г', состоящий нз п последовательных кусков; (Чо ''' Ч~) (Ч!.Р]з '''э Ч!)ю '''э (Ч! .!.! '''1 Ч]) причем для каждого 1 = 1, ..., и цепочка Ч, отли! чается от о]! только наличием черты над одним из вхождений символов и верхнего индекса О у остальных. При этом каждый кусок начинается применением правила 1-го рода, а на всех остальных шагах куска, если таковые есть, применяются правила 2-го рода. Поскольку о]„~У', из т], можно с помощью правил 2-го, 3-го и 4-го рода вывести о] . (Сначала следует «загнать» черточку в конец цепочки, затем применить правило 3-го рода, далее пользоваться правилами 4-го рода.) А.
Е. Г»зд«»З [гл. з СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ 66 ускОРение и сжатие ВНВодОВ Ясно также, что цепочку в словаре У можно вывести в Г из 1 только вышеописанным образом. Ввиду леммы !.2 из сказанного вытекает эквивалентность Г и Г', а также равенство Ог (и) = Зг(п). Остается оценить Тг. Пусть Р' =(Чз,, т!„) — произвольный полный вывод в Г', и пусть ть (й = 1, 2, 3, 4) — число шагов этого вывода, па которых применяются правила рода й (шагов рода А). Нам достаточно найти такую не зависящую от Р' постоянную 1, чтобы выполнялось неравенство тз < 1ть Действительно„длина соответствующего Р' вывода в Г равна ть а так как тз = 1 и тв —— ~т!в»( — 1, мы получим т = тв + тз + тз + тв «~ < (1+ !)тв+~з! ~ < (1+)+ !)т, (! — максимум длин левых и правых частей правил Г).
Пусть з1, — последняя цепочка вывода Р', содержащая вхождение символа из Л. Шаги 1-го и 2-го рода— это все шаги с номерами, не ббльшими 1з, и только они. Для каждого 1=0, 1, ..., 1» имеем з1,="„~а ьзн где Вз ььен 2»'наспех. Положим д, ~$з(в йз=й,— у, Если 1-й шаг 2-го рода, то Ьз — — 1, а если 1-го, то — е < Ьз <«О, где е — максимум длин левых частей правил Г. Очевидно, ь 2';й,-аи-а,=а„. Отсюда, обозначая через Хз сумму Ь| по всем шагам рода й, получаем тз Хз =йь Х, < Ыи+ет~ ( ~ти!+гт~ = ! ть !+ гт, «<(1 +'е) т,.
Доказательство закончено. Теперь мы можем показать, что для произвольной грамматики имеется возможность «сжимать» и «ускорять» ее выводы равномерным образом в любом наперед заданном отношении, лишь бы не нарушились неравенства (1) (стр. 59); для этого, разумеется, нужно перейти к другим, эквивалентным грамматикам. Стоит заметить (см.
ниже доказательства теорем 2,1, 2.2), что эти новые грамматики, вообще говоря, сложнее старой — имеют больше вспомогательных символов или правил, и сами правила могут быть длиннее, — причем усложнение грамматики оказывается тем сильнее, чем больше мы захотим упростить выводы, т. е. «сжать» или «ускорить» их. Это обычная ситуация — за простоту и удобство пользования устройством приходится платить усложнением его самого.
Т е о р е м а 2. ! (о сжатии выводов). Для любой грамматики Г и любого положительного действительного числа г можно построить грамматику Г', эквивалентную Г и такую, что Яг (п)<гпах(п, 1, гог(п)); Тг (и) «<Тг (и) + шах (сп, !). Доказательство. Пусть Г = (У, (з',1,зт). В силу леммы 2.2 мы можем считать, что левые части правил Г не пусты, и рассматривать только такие выводы в Г, в которых правило с пустой правой частью применяется разве что на последнем шаге. Пусть 1 — натуральное число, большее !/г и одновременно большее шах (ф( и шах ! )зр( — (ф! (. Соло« »Ф~Л Ф-в» =За ставим каждой цепочке аз ~(У ЦУ,,)*„! ьз (<21, взаимно однозначным образом новый символ а(ьз).
Множество таких символов обозначим Л. Каждому правилу ф - вР ~ )с, каждой цепочке ьз гн (У () Ф')', ! ьз !«<21, содержащей вхождения ф, и каждому вхождению 6 * ф * т) цепочки ф в в сопоставим правило ~=1(ф, зР, 6, т!) следующим образом: если !ЕвРт! (< 21, то )=а(ы)-»а(Кт1); если же ! $вР«1!> 21, то ~=а(ьз) — »а(~)а(ьз), где ь|ьз=вврз! и !~, (=1 (а(ьз) существует, поскольку ! 5 зрз! ! ( 31). Далее, каждому правилу ф-»вРен)с, каждой паре цепочек ьзн ьзз ~ (У () И')*, 1--! ьз, !< «21, 1<«! ьзз !< 21, такой, что ьььзз содержит вхождения вр, и каждому вхождению 5*ф*«! цепочки ф в ьььзз сопоставим правило д = д(ф, зР, 6, т!, ьзн ыз) следУющим обРазом; если ! ЕзРт!!< 21 (заметим, что в любом случае ! $вйз) (>1), то д = а(ьз,) а(ьзз)-»а($вРз)); если 21 ~! езйз) («<41, то д— =а(ы,)а(в,) — «аЯ,)а(ьз), где ь1ьз= звйз! и! ~, (=~ ~ ! ЕвРт! !( ! (( ) — целая часть); если, наконец, ДвРз! ! > 41, то у= а(ьзв) а(ьзз)- а(ьв) а(ьз) а(ьз), где йьзьз= ззрзЬ ! ~, )=21, ! ьз (=1 (аКз) существует, так как ! $зрт1(< 51).
3* 1гл. о СИГНАЛИЗИРУЮЩИЕ ЕУНКЦНИ ускОРение и сжьтйе въ|ВОДОВ Сопоставим также каждой цепочке ы, !о|! «= 21, правило Й = Й(о|): а(ы) — оо. Положим теперь Г' = ()', Я, а(1), )о'), где )с" состоит из всех правил ), д и Й. Покажем, что Г' — нужная грамматика. Назовем образом цепочки т,ен (Р ()УР)' любую це- почкУ 0 = а(оо!) ...
а(о|о) такУю, что о|! ... о|А = 11 и при Й ) 1 для каждого 1 = 1, ..., Й имеет место !о|1() 1. Из определения правил ! и д ясно, что если из цепочки у! непосредственно выводима в Г цепочка 1!э, то из каждого образа О| цепочки 11, будет непосредственно выводим в Г' некоторый образ цепочки то (с помощью некоторого правила и, если (О,( ) 1, н правила ), если (О|( = !).
Поэтому для каждого полного вывода Р = = (то..... т„) в Г существует вывод Р' = (Оо, ... ..., 0„) в Г' такой, что 0; есть образ т| для каждого | = О, ..., п (в частности, О, = а(Т)); при этом в си- 1 лу определения образа !011~~шах(1, — 1!Х|!). Из 0 можно с помощью правил Й вывести т, причем длины промежуточных цепочек в этом выводе не будут превосходить шах(1, )11„(). Таким образом, мы получаем вывод т из а(1) в Г, в котором максимальная длина це! почки не превосходит шах (! У,„(, 1, — |пах ! т! !), при!о<|<< чем число шагов этого вывода не больше и + /1 + шах! — ! т,„(, !) (число применений правил ! и д равно 1 и; число применений правил Й не превосходит при (т, ) ) 1 и единицы при (11„( ( 1). В то же время— по лемме 1.! — всякая выводимая в Г' цепочка в словаре у' может быть выведена так, что сначала будут применяться правила ! и д, а потом Й; отсюда ясно, что эта цепочка может быть выведена и в Г, Итак, Г' есть нужная грамматика.
С л е д с т в и е. Для любой грамматики Г и л>обого натурального числа Й можно построить грамматику Г', эквивалентную Г и такую, что 5г (п)(и|ах(и, 1, 5г(и) — Й)1 Тг (и):к Тг (и) + |пах(и, !). Т е о р е м а 2.2 (об ускорении выводов). Для любой грамматики Г и любого положительного действительного числа с можно построить грамматику Г', эквивалентную Г и такую, что Тг (и) ( |пах(1, сТг (и)); 5г (и) (5г(и). Доказательство. Пусть Г = (У,)Р',1,)(), В силу леммы о сцеплении мы можем считать грамматику Г сцепленной. Фиксируем натуральное число 1, большее 1/с, и рассмотрим всевозможные размеченные выводы в грамматике Г: Р'=(ы~, ..., о|'„Р оо„), о||=1,оч|,от!о удовлетворяющие условиям: (а) 1 ( и ( 21; (О) существуют такие 1| и 1о из ряда О, ..., п — 1, что з, =и, = =Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
