markov_teorija_algorifmov (522344), страница 53
Текст из файла (страница 53)
Тогда 6: ВТ9УС ! — ВТУЗС Б 'Р= ВиТЗС, что и оставалось доказать. З.З. Пусть М вЂ” слово в алфавите А,а)1, а 0 и Е— слова в алфавите Аиа[)у[гири[хо. Тогда 3) 5: Е['АМЕ )= 0МХЕ. ргл. у УМИВВРСАЛЬМЫЙ АЛГОРИФМ 2зт 'и (3.5] (3.21 (3.21 Но ЕХК~(~,ТгрКБ, Х ЕЩТ~рБ, т. е.
Доказывается правой индукцией по М. Для индукционного шага надлежит воспользоваться формулой подстановки, представленной 15-й строкой схемы алгорифма !о. 3.4. Пусть Л7 — слово в алфавите Лва()у, а Р и П вЂ” слова в алфавите АваРуфаф р. Тогда (4) 'В: Е рй!П ).= Ебрр. Доказывается правой индукцией по У. Для индукционного шага надлежит воспользоваться формулой подстановки, представленной 20-й строкой схемы алгорифма дз. 3.5. Пусть Š— слово в алфавите А,аР7, (г и Б — слова в алфавите А„а Т вЂ” слово в алфавите Абаруоз. Тогда (5) '!(: ЕА)збрТцьЯБ ~ И.О~Хгр~фБ.
Доказывается правой индукцней по !г. При пустом (г утверждение (5) тривиально. Пусть теперь для какого-либо Я в алфавите А, утверждение (5) верно для любых Ь, Т и Б, удовлетворяющих перечисленным в формулировке леммы условиям. Тогда для любой буквы я алфавита А, 3(: ич ат рф()~Б~= е),()раутя ()фР )- Е) ЯМТ рЯКБ 18 ~= ЕЛД( Тч4Ь|аБ (3. Ц )- Е).!75рт~дцфБ, в 'В: Е)4 ЮТ~рЮР)= и,орт~рдцБ, что и оставалось доказать.
3.6. Пусть Š— слово в алфавите Авару, (! и Б — слова в алфавите А„Т вЂ” слово в алфавите Аеару<о. Если !г не является началом Б, лто (6) 2): Е)ргдт рфБ Е'АОТ~Б. В самом деле, пусть выполнены условия леммы. Тогда существуют слова К, Яз и Б, в алфавите А, н буква э этого алфавита такие, что Я Х К$Я„Б ~ КБ, и слово Б, не начинается буквой ч. Имеем Ы р !3ТгрзЬБ Аг ГлрКЩтТгрфКБ, СЛУЧАЙ ДВУХВУКВВИМОГО АЛФАВИТА В: ЕЛРК5О,Т рфКБ,,= ЕЛК рт,т рКфБ, )- Е)КРАЯ тТ рКВ)Бт !8 ~= Шд„О,Т,рКргрБг з г К)йАЯ ТгрКуБ )= ЕАКГЗ О,Т руКБ, )- ЕХК"гу4.,ТугрКБт б ~ Е)К5-О,Т рКБ, )- И КН,ТгрКБ,.
!о и потому В: ИрОТ рфБ = Е) ОТ~Б, что и требовалось доказать. Положим теперь для произвольных слов Я и Б в ал- фавите А, Х (грфЯ, Я, Б) *), если !;) входит в Б, Бгрф, если Я не входит в Б. '"- '-( 3.7. Пусть Ь вЂ” слово в алфавите А,абу, (г и Б — слова в Аго Т вЂ” слово в Абадуго. Тогда (7) Е: и~ ОтрфБ)=Е)ч ОТП((), Б). Доказывается левой индукцией по Б. При пустом Б утверждение (7) тривиально, так как для любого (;! ПЩ, Л) ~грф.
Пусть для какого-либо Б в А, утверждение (7) справедливо при любых Ь, Т и !г, удовлетворяющих перечисленным в'формулировке леммы условиям. Покажем, что оно будет справедливо и'при замене Б на чБ, где ~ — любая буква алфавита А,. Если ВБ начинаетсЯ словом Я, то П Я, ьеБ) зь гРфВБ, н в этом случае утверждение 'В: Е)!(А(гТгрфэБ )= ьг48дТП (!г, ВБ) тривиально. '] Результат подстановки ЧпРЯ вместо первого вхождении О в 3 (см. 4 23,8, с.
!ОВ). (гл. у 289 УНИВЕРСАЛЬНЫЙ АЛГОРИФМ 288 $421 СЛУЧАЙ ДВУХБУКВЕННОГО АЛФАВИТА Рассмотрим теперь случай, когда $Б не начинается словом Я. Если Я не входит в $Б, то (Е не входит также и в Б, и потому П((),8Б)л.1Бфф, П(О,Б)~(Бфф. Если же Я входит в ВБ, то первое вхождение Я в $Б имеет вид $Б! 26Я 2КБ„где Б, и Б,— слова в алфавите А,, Но тогда Б,2(2Я 2КБ,— первое вхождение Я в Б, так что П Я, 9Б) х$БкфЩБ„ П ((3, Б) Х Б,ффОБ,. Следовательно, если $Б не начинается словом Я, то П(Я, ВБ) лс 9П((е, Б) В; Ир(~Т~рД$)= 7'ЩТ~ДБ [3.8~ )- ЫЯТуз!рфБ (2 )=('АРЯТ92р4рБ [3,2) (- (.~роТ8ф4рБ 8 )=7.Д(((,(Т$П ((,(, Б). НО $П ((к(, Б) л( П ((к!, 9Б) и, следовательно, В: (.Ар(~тфф5Б)=7.)рдтп((), р), что и оставалось доказать. 3.8.
Пусть Н вЂ” слово в алфавите Аоа(2(27, К и Б — слова в А„а Т вЂ” слово в Аоа()То!, Тогда (8) В: НрКТНБ (=НК(АТКНБ. Доказывается правой индукцией по К. При пустом К утверждение (8) тривиально. Пусть для какого-либо К в алфавите А, утверждение (8) справедли- во для любых Н, Т и Б, удовлетворяющих условиям, пере- численным в формулировке леммы. Тогда для любой буквы Б алфавита А, В: НрКВТХБ[= НКК~КНБ )- НК '6(АВТКНБ (8 ~= НКЪТКК Б [3. Ц )- НКгудтт Б, 4 т. е. В: Н(4КЕТНБ ~ НКЦАТК~нБ, что и оставалось показать.
Теперь докажем леммы 2.2 — 2.5. Доказательство леммы 2.2, Пусть Я вЂ” нормальный алгорифм в алфавите А„а Я— слово в этом алфавите. Тогда В. Чрн„д Р Я 6962< фЯ 26 )= й' Ч й Р.21 )- Хркд'62фф(,(, 1! т. е, В: 2('62(е (=)!(48Е" ффЯ, что и требовалось доказать. Дока за тел ь ство леммы 2 3 получается ствснным рассмотрением схемы алгорифма В. Д о к а з а т е л ь с т в о л е и м ы 2.4. Пусть выполнены условия леммы. Тогда (9) Я ф'А и непосред- В: (д.рЯМТК фБ)=и„ЦМТА( П(о, Б) Х Ь) р(;(Муй((ВБфф (= !'.Акгмуй(62Бф )- Ы(;(МТА((ВБ (8 Г- 1),ЯМТА(о(Б (9 )= 1ЛеМХТА(62Б (- 1, (Е МЪрй(тоирфБ 26 (= й Я МАууй((вффБ ) — 8 Я Мф(4 А(оурфБ 9 [3.71 [3.8, (9)1 [3.31 [3.2'[ первое вхождение Я в П ((',(, Б) 10 А. А, Марков, Н.
М. Ннгорнн6 т. е. ! В: Ы(АЯМТАГ62ффБ (= Щму)крд!(ВффБ, что и требовалось доказать. Д о к а з а т е л ь с т в о л е м м ы 2.5. Пусть т — буква алфавита ар, с, и А( — слова в алфавите А,а()у, (,(, К, Б — слова в алфавите А, и Я входит в Б. ! Пусть Б242 ЯжБ„где Б, и Б,— слова в алфавите А„— Б. Тогв,а =Е(фЯ, Я, Б) 3( Б,ффЯБ,.
$441 РННВЕРСАЛЬНЫй АЛГОРИФМ [гл. т ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 6: Т.АРЯХ)туйа!Р4)!5 ~Т.ХРЯХЯТА7аП((), 5) [3.71 хе ).хрЯХР7%.5,4„)Ц5, )= 1.Хф~Х)777уьь5,!(1;27(75, [3.5~ [- 5Х 0)АХ)!уй(а5,!В~7(75, 1Э )= ~дХ)ьхр у 5,4,~>ф5, [3.31 ) — ~ ЯХ)4)<7 Уа51474,"1!)54 1О )= 5 ЯХ)41<7АСа514В7(75, [3.41 ) ь44Хр)<71та5~хз~ 21 ) — Л 44Хр)477 57а51я54 23 ~= Т.151<р7%о5,Т<к5, [3.81 ) — (-ЯХРруй(а5ЯТ5.
24 )= 1.ффрту%о5Я5, [3,21 )- 7.ОХИ)Уа5,И, 10 АЯхйуИ!о~(Р, Я,5). Так как а ь а, то утверждение а) леммы 2.5 доказано (достаточно в предыдущем рассуждении в качестве х взять а). Завершим теперь доказательство утверждения б) (здесь х-х()). В: 1.(фКуй(ах Я, 7~, 5) 1 — (.ЯТОД7%ое (Я, 9„5) ' — т1.ЯОРуА7аХ (Я, <), 5) [3.21 1 — Х)17.(2ОЯ757аХ (Я, Я, 5) 11 1 — )44ЩР1<у)2*а'л' ()<, 9, 5) !4 [="А)ьр1.7,71< 71)ь74 (Р4, Я, 5) [3 21 )- !рай.
!',) А!7)раХ Я, Я, 5) 7 )= ч: ~ Я, <г, 5) [3.41 )- пХ(К, Я, 5), 22 прн этом слово пХ(1<„Я, 5) не поддается алгорифму 4). Таким образом, доказательство теоремы 2.1 закончено. й 44. Доказательство теоремы об универсальном алгорифме 1. Перейдем теперь к доказательству теоремы з 42.1.1. Пусть длина рассматриваемого нами алфавита А равна п. Символом а! (1(1 н) мы условимся обозначать его 1-ю букву. Введем операцию [Р' перевода слов в алфавите А, определив ее следующими равенствами: [Ат [Рит [Р4иЬси (здесь Р означает произвольное слово в алфавите А, удовлетворяет условию 1 "1(п, а а и Ь суть буквы введенного нами в начале ~ 43 алфавита А,).
Условимся далее для любого нормального алгорнфма Й в алфавите А обозначать посредством 21' его перевод Ц 41.61 в двухбуквенный алфавит А, в соответствии с только что описанной операцией перевода слов. Введем две новые буквы е и р, отличные от букв алфавита А и от всех букв, введенных в п. 1 3 43. Рассмотрим нормальный алгорифм Св в алфавите ААьа()уберпп со следующей сокращенно записанной схемой: Ьа,, — а1 па — а„п Ьп где 1(! < п, а Ь пробегает алфавит ару. Мы стремимся доказать следующее утверждение: 1.1. Пусть 2( — нормальны!! алгорифм в алфавите А, а Р— слово в А. Тогда: а) чь. ар!11!76Р~ 21 т ие[Р! б) 6: п[Р')=Рп.
1О. раьп а„п ра, — Ьаар аЬРЬ арь ьар арб ()увар — Ьрь паЬ вЂ” рп, <1> <2> <3> <4> <5> <6> <7> <8> <9> <10> 292 унизепсхльный ллгопиом [гл, ч 2. Для . Для этого мы предварительно докажем следующие леммы 2.1 — 2.6. 2.1. П .. Пусть каждое из слов Х, 1' является словом в одном из алфавитов Ааруб, А,аруал. Пусть 1<1<и. Тогда (1) 6; ХЫра У)=ХЫ+с 'ра,У'. Доказывается арифметической индукцией по й Действительно, для 1=-1 утверждение (!) тривиально. Пусть теперь для какого-либо 1 (1<1<я) утверждение (1) справедливо для любого 1 и для любых Х и У, удовлетворяющих перечисленным в формулировке леммы условиям.
Тогда 6: ХЫраги,У 1 — ХЫ"'рба,и,У 1- ХЬУ. Р,.У 1 ~= ХЫ+'ра„У [инд. предпол.1, т. е 6: ХЫРаь„У)=- ХЫисра 1, что и оставалось доказать. 2.2. П усть Р— слово в алфавите А, И вЂ” слово в алфа- вите Аиа1)уз, У вЂ” слово в алфавите Ааруб, Тогда (2) 6: ПарРУ~=П[Р' рУ. Доказывается правой иидукцией по Р. ви н. Действительно, для пустого Р утвержден е (2) и ) три- сп аве аль о. Пусть теперь для какого-либо Р утверж (2) дение р дливо для любых П и У, удовлетворяющих перечис- ленным в формулировке леммы условиям, Пусть 1<1<и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
