markov_teorija_algorifmov (522344), страница 46
Текст из файла (страница 46)
Последний член цепи О алгорифм 6 по условию перерабатывает в пустое слово. Поэтому на основании теоремы 3.1 (Я([6)(Р)м Й (Р), что и требовалось ПОВТОРЕНИЕ АЛГОРИФМА 245 3. 22. Если 6 (Я (Р)) д' Л, то (Я ( ) 6) (Р) (ЯГ [6) (Й (Р)). В самом деле, в предположении 6(Я(Р)) ф: Л нетрудно показать что. 1'. Если слово (г таково, что 6 (Я) о Л, а Я вЂ много- ленная итерационная цепь алгорифма Й, соединяющая (Р) с [г и такая, что алгорифм 6 перерабатывает всякий ее внутренний член в непустое слово, то у-система ТРЯ является многочленной итерационной цепью алгорифма Й, 'соединяющей Р со словом чг и обладающей тем свойством, , что алгорифм 6 перерабатывает всякий ее внутренний член в непустое слово.
(Заметим, что по сравнению с 8 система ТРБ обладает еще одним внутренним членом Й (Р), но ал, горифм 6, по предположенному, перерабатывает этот член в непустое слово.) 2'. Если слово Я таково, что 6([',[)~Л, а 5 — много: членная итерационная цепь алгорифма Я, соединяющая Р с (4 и такая, что алгорифм 6 перерабатывает всякий ее внутренний член в неп устое слово, то 3 имеет вид уРуЯ(Р) Т[1у, где Т вЂ некотор у-система, и потому у-система ТЯ(Р)Т[гу является многочленной итерационной цепью алгорифма Я, соединяющей Я(Р) со словом Я и обладающей тем свойством, что алгорифм 6 перерабатывает всякий ее внутренний член в непустое слово.
(Легко видеть, что всякий внутренний член „урезанной" системы ТЯ (Р) Т [[у является внутренним членом 3.) Исходя из 1' и 2', нетрудно доказать интересующее нас условное равенство (Й~ )6) (Р) (Йг [6) (Й (Р)). Детали рассуждения мы оставляем читателю. 4. В теореме 3.1 речь идет о повторном применении данного нормального алгорифма до тех пор, пока не получится слово с желаемым свойством, причем само исходное слово не испытывается на это свойство. Может, однако, оказаться нужным начать испытания на желаемое свойство уже с самого исходного слова. Процесс заканчивается в этом случае на исходном слове, если оно обладает этим свойством.
Если же оно им не обладает, то к нему применяется алгорифм Й и далее процесс идет, как описано выше. Этому видоизменению повторения алгорифма Й, управляемого 6, соответствует следующее видоизменение теоремы 3.1: 4.1. Каковы бы ни были нормальные алгорифмы Я и 6, может быть построен нормальный алгорифм л.[ над объединением А их алфавитов со следуюи[им свойством: А! тогда и только тогда перерабатывает слово Р в алфавите А 246 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ !ГЛ. !Ч в слово !е, когда 6 (!е) ль Л и существует итерационная цепь 5 алгорифма Й, соединяющая Р с 1~ и такая, что 6 перерабатывает в непустое слово все члены 5, за исключе- нием последнего. Тео ема 4.1 м рема 4.1 может быть доказана следующим об а о р зом.
— р извольные нормальные алгорифмы; го и м 8 на — объединение их алфавитов, Построим нормальный а . р ф над А согласно теореме 3,1 таким образом, л. ладал своиством, указанным в этой теореме. Построим тождественный нормальный алгорифм 3 в алф- А а- [9, 1. К алгорифмам 3А, 2) и 6 применим теорему разветвления [~ 39.1.Ц. Построим, согласно этой теореме, нормальный алга и р " алгорифм А! над объединением алфавитов этих алгорифмов, т. е.
над алфавитом Б алгорифма 6, таким условия: р, ! для любого Р в Б соблюдались следующие (1) если 6(Р)ХЛ, то Я)(Р) ЗА(Р), (2) если 6(Р) ~~"Л, то ~О(Р)- я)(Р), (3) если З применйм к Р, то и 6 применйм к Р. гда З является искомым алгорифмом. В самом деле, Б является расширением А, так как В есть алга ифм на А р ф д А и вместе стем алгорифм в Б Поэтому как алгорифм над Б есть алгорифм на А. Пусть Р в А, в А, и пусть л! (Р) а (!. Тогда х! применйм к Р, ад и потому 6 применйм к Р [(3)!. Пусть 6(Р)кЛ.
Тогда л)(Р)ХР[(1), 9 28.41. Поэтому Рм.!е, н так как 6(Р) ~Л, имеем 6((е) л. Л. Положим 5 есть -систе у- тема в алфавите А с первым членом Р и последним членом !',1. Ни в силу чего 5 есть и !,1. Никакое слово вида УХУ)'у не входит в 5, у ть итерационная цепь алгорифма й Ц 9!. не имеет членов, не в, не являющихся ее последним членом. оэтому алга ифм 6 в непустое слово $ 91. р ф 6 перерабатывает всякий такой член 5 Пусть теперь 6(Р) ~ЕЛ.
Тогда ь!(Р) В(р) [(2)1, и потому 8(Р)Х!е. Согласно построению алгорифма 6 имеет что перерабатывает в ний член. Йо 6 пе е ает в непустое слово всякий ее внутренрерабатывает в непустое слово и первый ПОВТОРЕНИЯ АЛГОРИФМА член 5 — слово Р. Следовательно, 6 перерабатывает в не- пустое слово все члены 5, за исключением последнего. Таким образом, мы доказали, что коль скоро для слова Р ,в А имеет место равенство л.'(Р)м. Я, соблюдается условие 6(!е) Аь Л и существует итерационная цепь 5 алгорифма 2(, ' соединяющая Р с Я и такая, что 6 перерабатывает в не- , пустое слово все члены 5, за исключением последнего. Допустим теперь, что для слов Р и Я в алфавите А соблюдается равенство 6 Я) м.
Л и существует итерационная цепь 5 алгорифма Й, соединяющая Р с !',! и такая, что 6 перерабатывает в непустое слово все члены 5, за исключением последнего. Докажем, что тогда имеет место равенство З(Р) Х Я. Так как всякий внутренний член системы 5 не является последним членом этой системы, то алгорнфм 6 перерабатывает в непустое слово всякий внутренний член 5. Найдем объем [5' системы 5. Так как 5 соединяет Р с Я,[5' ) 1. Рассмотрим два случая: [5' = 1 и [5' ) 1.
В первом случае очевидным образом Р Я.1~, и потому 6(Р) м Л. Так как ВА(Р) Л.Р [9 28.41, имеем А!(Р) ~ Р [(1)1, и так как Рль Я, л!(Р) Х (). Во втором случае система 5 многочленна. Согласно построению алгорифма л) имеет место равенство 2)(Р)АА!е. Система 5 имеет первый член Р, который не является ее последним членом, Поэтому 6 перерабатывает Р в непустое слово и мы имеем !А!(Р) х !е [(2)1! Это завершает доказательство теоремы 4.1. б. В теоремах 3.1 и 4.1 шла речь о доведении итерационных цепей до члена, удовлетворяющего некоторому алгорифмически проверяемому условию. Аналогичным образом в теореме 8,1 речь пойдет о доведении итерационной цепи до данного Объема.
В этой теореме будут фигурировать слова вида !!!' ж Р, где )У вЂ натуральн число, а Р†сло в данном алфавите А (мы будем предполагать, что ч! ие является буквой А). Слова этого вида можно рассматривать как пары, первым членом которых является натуральное число, а вторым— слово в данном алфавите. Буква С в теореме 5.1 Означает двухбуквенный алфавит )ч!. 5.1. Каков бы ни был нормальный алгорифм 6 в ал4!а- вите А, может бьапь построен нормальный алгорифм В над ал!рогатом А В С такой, что равенство 3 ()ч' !ь Р) Х !е 248 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИфА4ОВ тогда и только тогда имеет место для слова Р в А и натурального числа М, когда существует итерационная цепь объема М+1 алгорифма й, соединяющая Р с Я.
Докажем эту теорему. Пусть (2) Б=АОС, а — буква, не входящая в Б, 13) В =Ба. Построим нормальные алгорифмы 6, 6 и $ в алфавите В со схемами а!- аж$ — аж аж— а, 6. (ж5 ж, ж 6: где литеральная переменная $ пробегает алфавит Б. Легко доказываются следующие пять лемм, в которых М означает произвольное натуральное число, Р— произвольное слово в алфавите Б. 5.2. 6 ((М + 1) ж Р) Ас М * Р. 5.3. 6(жР) и Л. 5.4. 6(М жР) о Мж. 5.5. ф~ (М ж Р) Х Р.
Построим нормальные композиции (6о6) и (е(о$). Это нормальные алгорифмы над алфавитом В, Пусть (4) ф = ((6 об)"(й о4у)) [4 38.6(. ,49 — нормальный алгорнфч над В Ц 38.6.21. Докажем 5.6. Если (5) Е (Р) ~'- 14, то для любого натурального числа М 6) .~д((М+ 1)*Р) хМж д. В самом деле, пусть имеет месго равенство (5). Тогда Р есть слово в алфавите А и мы имеем (?) ((Р о 6) ((м+ 1) ж Р) х м ж 4 403 ПОВТОРЕНИЕ АЛГОРИФМА 249 ля любого натурального числа М[5,2, 5 4]. Далее, имеем 8) Ь((М+1) жР)~Р [5 Ч (9) (йод) ((М+ 1) ж Р) хе Я [(8), (5)1 и равенство (6) [(7)„(9)1.
Имеет место также 5.7. Если 1г1(Мж)с), где М вЂ” натуральное число, а Я— слово в алфавите А, то !Й (14) [(4), 9 38.6.3, 9 37.4.3, 5.51, Пусть теперь Г означает алфавит алгорифма $. Построим нормальный алгорифм л' согласно теореме 4.1 таким обра,зом, что равенство Ж(Р) АА Д, где Р— какое-нибудь слово в алфавите Г, будет иметь место тогда и только тогда, когда (Р3) 6Я) хЛ и существует итерационная цепь Т алгорифма г..1, соединяющая Р с Я и такая, что 6 перерабатывает в непустое слово все члены Т, за исключением последнего.
Построим нормальный алгорифм Э как нормальную композицию хл и Я: (11) 4А =- (ЬоЗ). , Покажем, что 4В удовлетворяет условию, формулированному в теореме 5,1. Докажем для этого лемму 5.8. Если имеет место равенство (1), где М вЂ” натуральное число, а Р— слово в алфавите А, то существует ите. рационная цепь объема М+ 1 алгорифма 6, соединяющая Р с Пусть условие 5.8 выполнено для каких-либо фиксированных М, Р н 4Е.
Ввиду (11) и (1) существует слово 77 , такое, что ' (12) лэ(МжР) ~)7 (13) 6(М) ~ Я. Согласно построению алгорифма А', имеем (14) 6 (14) Аг Л и существует итерационная цепь Т нормального алгорифма $, соединяющая МжР с М и такая, что алгорифм 6 перерабатывает в непустое слово все члены Т, за исключением последнего [(12)1. Докажем, что всякое натуральное число К, меныпее или т вное М, удовлетворяет следующему условию Р: 250 сочетАния ногмхльных АлгогиФмов [гл. ю «существует итерационная цепь алгорифма Й с первым членом Р, с объемом К-)-1 и таким последним членом Х, что слово ()У вЂ” К)ЖХ есть (К+!)-й член цепи Т».
Число 0 удовлетворяет условию Р, В самом деле, слово уру является итерационной цепью алгорифма Й тривиаль- ным образом; Р является первым членом этой итерационной цепи, объем которой равен 1, последний член цепи уРу есть Р и )УЖР есть первый член цепи Т. Допустим теперь, что некоторое число К, меньшее 1«', удовлетворяет условию Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
