markov_teorija_algorifmov (522344), страница 34
Текст из файла (страница 34)
3.4. Если Р и Д вЂ” слова в АБ, то (11) [Рй' *[Р'+[дв+(Пр хала). Фиксируем Р и докажем правой индукцией по а(, что всякое слово Я в АБ удовлетворяет равенству (11). Пустое слово удовлетворяет ему, так как, очевидно, [Л" О, ПЛ~.-О. Чтобы доказать лемму, нам поэтому надо лишь дока- зать, что соблюдение равенства (11) для какого-нибудь слова )с в АБ влечет соблюдение равенства [Р1»ввв,[Р»+ф~в 1 (ПРБдХПР~Ад) для любой буквы ь алфавита АБ. Итак, допустим, что равенство (11) соблюдается, причем Я есть слово Б АБ.
Пусть также Ь вЂ” буква АБ. Имеем (12) [[Ргхь [[РАа 1 [[вьхь (1з) ПРД ' = Првь+ ПД~, [Рд~' [рд» 1 (Прдэах П~Аа) [3 3) ° [Р'+ [д'+(Прад х Пдлд)+ ((ПР' + ПД ) х В" ) [(11), (1З)1 [р'+[д'+(Пд хц~ )+(Првьх(цд +П~"а)) [Р'+[)7Г 1 (ПрааХПК~Аа) [3 3 (12)1 что и требовалось доказать. ;,а асч АЛГОРИФМЫ ПОБУКББННОГО КОДИРОВАНИЯ !77 3.5. Для любых слов Р, (Е и Я в АБ ,;. [РСЕ)тв ~ [Рв + [('!в 1 [Рв+ (ЦРБдХ П()Аа) (ПрвахцЯАа) 1 (ПЯБахцДАа) В самом деле, имеем :,вв [Р()Р [Р1~! +[К +(ПРЯБахцйвд) [3 4~ -[Р +% +(ПРБдхПЮАа)+ Р +(ПРБ[() хцр"') [3.41 [рв„( [() 1 [1зв+ (Прад х П два)+ ((ПРБ'+ ПЯБд) х Пдль) -[ +я +[я +(Пр-хПЕ"')+ (Првь Х ПРАа)+(П Евь Х 1РАа) 3.6.
Если [Рв О, то существуют такие слова (1 и Я »(з в сифавитах А и Б соответственно, что Рл.!',»)с. 4. Пусть, в самом деле, [Р' О для некоторого слова Р Рз в алфавите АБ. Если в это слово не входят буквы алфавита Б, то Р есть слово в А и можно положить Я Х Р, ЯХЛ. Допустим, что в Р входят буквы алфавита Б. Пусть тогда (Е»БЧ»Б'О' — первое вхождение буквы алфавита Б в Р. !е есть тогда слово в А, т! — буква Б. Если бы Т»Б~»РУ было вхождением буквы $ алфавита А в Я, то мы имели бы Ечв Х(ЯТ~(7 и слово т!Т$, где $ — буква А, т! — буква Б, входило бы в Р вопреки тому, что [Р" О, Следовательно, никакая буква алфавита А не входит в 5 и 3 есть слово в Б. Остается положить )сйт~5, чтобы иметь Рй!Я, где !е — слово в А, )т †сло в Б.
3.7. Если Я вЂ сло в А, й †сло в Б, то [(тс А ~~ [ф~в~К,' Это очевидно из определения проекций. 3.8. Если [Р'. О, то РХ[РА[РБ, Это следует из двух предыдущих лемм. 3.9. Если [Р' О, то А»А, Б: 1' ~. В самом деле, если [Р' О, то никакие слова вида т)Я (3 †бук А, т! †бук Б), т. е. никакие левые части фор- 178 НОРМАЛЬНЫЕ АЛГОРИФМЫ [гл. мул подстановок алгорифма ВА Б, не входят в Р. Это слово тогда не поддается ВА, в.
3.10. Если [РвчьО, то существует такое слово (е, чта ВА,,': Р)-Е. Пусть, в самом деле, Р— слово в АБ и [Рв-е-О. Тогда в Р входит слово вида 111т9, где $ — буква А, и — буква Б. Пусть Е Ж ЧРтя Ж Т будет вхождением такого слова в Р.
В слово ЧЯ$ входит буква алфавита А, Пусть УЖЬЖ'ввпервое вхождение буквы алфавита А в Ч)ск. Тогда У)~А, так как ь Л'71. У есть слово в алфавите Б, Следовательно, У имеет вид Ф'д, где 7 — буква Б. Имеем поэтому Ьтт м БЩУТ и тхжт. Таким образом, в Р входит слово х~, где ь" — буква А, у — буква Б, т. е.
в Р входит левая часть одной из формул подстановок алгорифма ВА Б. так как все формулы подстановок этого алгорифма простые, алгорифм просто переводит Р в некоторое слово Я, что и требовалось доказать. 3,11. Если ВА, Б. .Р[ — Я, то Я'=[Р' — 1, [Я~Х[РА, [()Б ~ [РБ В самом деле, пусть ВА, в..
Р) — 1~. Тогда первый шаг применения алгорифма ВА, в к слову Р состоит в подстановке правой части св1 одной из формул подстановок алгорифма вместо первого вхождения ее левой части ц$ (9— буква А, 11 — буква Б). Пусть 1сЖтДЖŠ— первое вхождение зД в Р. Тогда Р тг 7(тДЕ, ~хЯЧЕ. Принимая во внимание, что по определению высоты [~Д'= 1, дч =о' и что [[Б„Аг [[е„вг [[„БАг [[„евг получаем, согласно 3.5, [Р -Р +1+[я+[[РБ +([Рзг Х [[9Аг)-+УАг, [е7в [Авв+[Ов+[[над 1 (Увел УАг)+УАг Огкуда [Яв=[Рв — 1. ':ввм АЛГОРИФМЫ ПОБУКВЕННОГО КОДИРОВАНИЯ Принимая далее во внимание, что [$11А 9г. [т)Р Х $, 179 получаем [РА Б [ОА1 [ОА ~[()А Аналогичным образом убеждаемся, что [РБХЯБ.
3.12. Алгорифм ЙА, Б применйм к любому слову в АБ. В самом деле, согласно 3.9 он применйм к любому .слову высоты нуль. Пусть теперь )е' — какое-либо натуральное число. Предположим, что 2А Б применим ко всякому слову 1е в АБ такому, что [ве'=А), и пусть Р— слово в АБ такое, что [Р'=)в"+1. Покажем, что ВА, Б применим к Р. Действительно, [РАФО, и, значит, существует такое слово Я, что ВА, Б. 'Р1 — (е [3.!0]. согласно 3.11 [Аг'=У, и потому алгорифм В», в применим к ~. Но тогда он применим и к Р [9 25.8.9]. Следовательно, ВА, Б применим к любому , слову в АБ, что и требовалось доказать. Покажем теперь, что (14) ВА, в (Р) Х[РА [РБ , для всякого слова Р в АБ. Пусть, в самом деле, Р— слово в АБ. Алгорифм ВА, Б , применим к Р [3.12].
Следовательно, существует 1~ в АБ , такое, что В~, Б(Р)Х(Е. Ясно, что (15) В.,,:;~Е~ н что в7 — слово высоты нуль [3.10]. Индукцией по шагам работы алгорифма ВА, Б с использованием 3.11 легко пока- зать, что (16) [РА — [()А (17) [РБ У [()Б Так как фв О, имеем (18) О~[ОА[ОБ Таким образом, ВА, в (Р) х (е' вА[1;1А [1е [(18)] Х [РА [РБ [(16), (17)]. Следовательно, ВА Б(Р)х~Р'[РБ, что и требовалось до. казать, 180 НОРМАЛЬНЫЕ ЛЛГОРНФМЫ [гл. Рн Формулируем здесь одно следствие, применяемое в дальнейшем. 3.12.
Если Я вЂ” слово в А, Я вЂ” слово в В, то (19) Вл, ь(У(е)~ (Ж. В самом деле, при этих условиях [щам я, [о()в тг р и потому (19) следует из (14). Соотношение (14) позволяет нам охарактеризовать Вл, ь как алгорифм двойного проектирования. 2 34. Некоторые арифметические алгорифмы 1. Построим теперь некоторые нормальные алгорифмы, работающие над натуральными числами и системами натуральных чисел. Отсюда до конца параграфа М, У, Я, )1, 3 означают переменные для натуральных чисел, представленных как слова в алфавите 1. Зададим нормальный алгорифм Ит в алфавите 1:«схемой «с Этот алгорифм перерабатывает пару натуральных чисел УФМ в абсолютную величину разности этих чисел, т.
е. (2) И, (У*М) х1У вЂ” М1 для любых натуральных чисел У и М. Действительно, из рассмотрения схемы (1) имеем 1.1. И,: М1Ф1У1 — МФУ. 1.2. И„: МФ)- М. 1.3. Й,: «М 1- М. 1.4. И~.' М 1. Кроме того, правой индукцией по У с использованием 1.1 и равенства У!Х! У могут быть доказаны следующие утверждения: ~1.6. И: муФу)=мж. 1.6. Ит: У:«УМ )= ж М. А теперь утверждение (2) доказывается следующим образом, зл1 нькотогыв лгнематнчьскиз ллгогифмы ~81 Если Уч.:;М, то УЖМхгУ:«У1У вЂ” М! и Й,: У4сУ1У вЂ” М1~=ж1У вЂ” М! [1.6] )- ! У М 1.] [1.3, 1.4]. Если же У) М, то УФМХ1У вЂ” М1М«М и Й,: ! У вЂ” М1М:«М)=1У вЂ” М1:«[1.5] ~=! У вЂ” М1 1 [1.2, 1.4].
, В обоих случаях, следовательно, Й, (У Ф М) лг1 У вЂ” М 1, : что и требовалось доказать. В частности, И,(М Ж У)я.Л тогда и только тогда, когда М лгУ, 2. Зададим далее нормальный алгорифм И, в алфавите ! ' схемой (1) 1П И!- Покажем, что он перерабатывает всякое натуральное число в остаток от деления этого числа на 5. В самом деле, из рассмотрения схемы (1) непосредственно усматривается справедливость следующих лемм: 2.1. И;. У+51- У. 2.2. Если У < 5, то И;.
У~. Из 2.1 вытекает 2.3. И;. 1с+ 5 х 9 ~= 11. Пусть теперь У вЂ” произвольное натуральное число. Представим его в виде У+5х Я, где У вЂ” остаток, Я— частноеотделения У на 5. Так как У У+бхай и У<5, алгорифм Й, в применении к слову У работает следующим образом: И;. У 1= Я 1 [2.3, 2.2], откуда Й,(У) хУ, что и требовалось доказать.
В частности, И,(У) ХЛ тогда и только тогда, когда У делится на 5. 3. Зададим теперь нормальный алгорифм Й, в алфавите ж схемой АППП!-1ж «с! 182 НОРМАЛ ЬНЫЕ АЛГОРИФМЫ [гл. п~ .; гзм НЕКОТОРЫЕ АРИФМЕТИЧЕСКИЕ АЛГОРИФМЫ 183 Покажем, что он перерабатывает всякое натуральное число У в неполное частное от деления У на 5, т. е. в ~ — ~ В самом деле, из рассмотрения схемы (1) легко усматривается справедливость следующих лемм: 3.1.
Й,: Ухч(М+5) ) — (У+1)КМ. 32. Если 0<М<5, то Й,: УжМ ) — УФ(М вЂ” 1). 3.3. Й,: Уж)- У. 3.4. Йз1 У 1- ФУ. Из 3.1 вытекает 3.5. Йз1 УФЯ+5З~Д) )==(У+(г)зКзч. Из 3.2 вытекает 3.6. Если У < 5, то й,: ржу~=дж. Пусть теперь У вЂ произвольн натуральное число. Представим его в виде Я+5хЯ, где Я вЂ” остаток, частное от деления У на 5. Так как У У+5Х Я и У < 5, алгорифм Й, в применении к слову У работает следующим образом: Й,: У) — чч(Р+бх ф [3,41 ~ЯФЯ [3.51 [3.61 )- Я.
[3.31 Таким образом, й,: У)= 1г, откуда й,(У)Х9, что и требовалось доказать. 4. Легко также построить нормальный алгорнфм в )Ф, перерабатывающий всякое натуральное число У в пару 1гФЯ, где Я вЂ” частное от деления У на 5, У вЂ” остаток от этого деления. Зададим, в самом деле, нормальный алго- рифм й, в [ж схемой *! ПП-!ж Ф- Ж вЂ” > яч, Этот алгорифм работает указанным только что образом, как читатель без труда докажет. ') Прямоугольные скобки прнменнютсн здесь длн обознзченни Велоя части.
Делитель 5 в трех предыдущих примерах взят только для определенности. Такие же нормальные алгорифмы можно, очевидно, построить для деления иа любое другое, отличное ,' от нуля натуральное число. Для этого надо только заменить пять черточек в левой части первой формулы каждой из трех только что рассмотренных схем соответствующим другим числом черточек. Если бы мы, однако, попытались построить 1- аналогичные алгорифмы для деления на нуль, совсем отбрасывая черточки в левой части первых формул этих схем, то, как 4 нетрудно видеть, мы получили бы алгорнфмы, не применимые ни к какому натуральному числу, что, разумеется, вполне соответствует сущности дела.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
