markov_teorija_algorifmov (522344), страница 47
Текст из файла (страница 47)
Покажем, что К+1 также удов- летворяет Р. Имеется итерационная цепь Е нормального алгорифма Й с первым членом Р, с объемом К ! 1 и с таким последним членом Х, что (й( — К)ЖХ есть (К-! 1)-й член Т. Так как К < А!, число А' — К положительно. Х есть член итерацион- ной цепи О алгорифма Й в алфавите А, в силу чего Х есть слово в алфавите А. Имеем (15) ь( ((у К) Ж Х) ц ((й7 К) 1) Ж Х !5.2]. Таким образом, алгорифм 6 перерабатывает (й! — К) * Х в непустое слово и в силу (14) имеем (16) (М вЂ” К) Ж Х ~ )7. Следовательно, (А! — К) ЖХ не есть последний член цепи Т, ввиду чего (й! — К)ЖХ соседствует слева в Т с некоторым членом 2 цепи Т.
Так как Т вЂ итерационн цепь алго- рифма Й, (17) ,В((л — К) жх)хг и, следовательно, (18) !ф ((А' — К) Ж Х). Поэтому 1Й(Х) !(18), 5,7] и имеется слово 1' такое, что (19) Й (Х) я. 1'. Построим (20) (7 — Я'у, (7 есть итерационная цепь алгорифма Й с последним членом У. Имеем (21) 9((й( — К) ЖХ) Х(й7 — (К+1)) Ж У ~(!9), 5 6], в силу чего Лъ ()у — (К+1))ЖУ у7), (21)]. Отсюда следует, что Ж У является последним членом цепи Т.
Следовательно, (22) Ж У»А )7. Отсюда (23) Поэтому ф(Я) хУ ~5.5, (22)] 1 х Ц !(28), (18)]. Таким образом, йт есть искомая итерационная цепь алгорифма Й, соединяющая Р с Я и имеющая объем й!+1. . Лемма 5.8 доказана. Теорема 5,1 будет доказана, если мы докажем лемму 5.9. Если г) — натуральное число, Р и !е — слова в алфавите А и существует итерационная цепь объема л!+1 алеорифма Й, соединяющая Р с Я, то имеет место равенство (1). В самом деле, пусть выполнены условия этой леммы.
Пусть Ф' — итерационная цепь объема й(+1 алгорифма Й, соединяющая Р с !',!. Докажем, что всякое натуральное число К, меньшее или равное А!, удовлетворяет следующему условию бй «существует итерационная цепь алгорифма 9 объема К-1-1, соединяющая слово У Ж Р со словом (й! — К) ж Х, где Х является (К+1)-м членом )У». мй ПОВТОРЕНИЕ АЛГОРИФМА 25! аким образом, (У вЂ” (К+1))ЖУ есть член итерационной епи Т алгорифма $.
Объем цепи (7 очевидно на единицу льше объема цепи Е !(20)], т, е. он равен К+2. Первый :член цепи У совпадает с первым членом цепи 3 [(20)], т. е. первым членом цепи У является слово Р. Последним членом цепи (7 является слово У !(20)] такое, что слово (й! — (К+1))ЖУ есть член Т. Мы доказали таким образом, что число К+1 удовлетворяет предикату Р, коль скоро число К, меньшее й(, удовлетворяет ему.
Тем самым доказано, что всякое натуральное число, не превосходящее л7, удовлетворяет этому предикату. В частности, ему удовлетворяет л(, т. е. существует итерационная цепь (У нормального алгорифма Й с первым членом Р, с объемом )у+! и с таким последним членом У, что слово ЖУ есть член Т.
Будучи членом итерационной цепи алгорифма Й в алфавите А, У есть слово в А. Поэтому 0г (Ж У) ~ А 15,8]. зз! 252 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ [ГЛ. ГР ПОВТОРЕНИЕ АЛГОРИФМА Число О удовлетворяет условию 6. В самом деле, слово ТУФРу есть итерационная цепь алгорифма $ объема 1, соединяющая слово Уч.Р с самим собой, причем Р есть 1-й член )Р'. Допустим, что число К, меньшее У, удовлетворяет 6. Тогда имеется итерационная цепь Т алгорифма ф объема К+1, соединяющая слово УФР со словом (У вЂ” К)жХ, где Х вЂ” (К+1)-й член (р'.
Так как К < у, то К+ 2 < у-1-1, т. е. К+2 <[)Р' . Поэтому существует член )' цепи )Р" с номером К+2. Так как Х есть член 11г с номером К+1, Х соседствует слева с У' в )Р. Так как )(Р— итерационная цепь алгорифма 6, имеем 2((х) лгу', в силу чего (24) ~((у — к)жх) о (у — (к+1))ж)' [5.6].
Так как Т вЂ” итерационная цепь алгорифма $, соединяющая У РАР с (У вЂ” К) ж Х, слово (У вЂ” К) ж Х есть последний член Т. Поэтому Т (У вЂ” (К+ 1)) Ф 1 у есть итерационная цепь зр объема К+2 с последним членом (У вЂ” (К-1-1)) ж 1'[(24)]. Первый же член итерационной цепи Т(У вЂ” (К+1))Ф)'у совпадает с первым членом Т, т. е. с УФР. Таким образом, Т(У вЂ” (К+1)) ж)'у есть итерационная цепь алгорифма 9 объема К+1, соединяющая УжР с (У вЂ” (К+1))ж1', где 1' — член цепи (Р' с номером К+2. Мы доказали, что коль скоро натуральное число К, меньшее У, удовлетворяет условию 6, натуральное число К+1 также удовлетворяет ему. Следовательно, всякое натуральное число, меньшее или равное У, удовлетворяет условию 6.
В частности, У удовлетворяет условию 6. Это означает, что существует итерационная цепь 5 алгорифма 9 объема У+1, соединяющая УФР со словом ФХ, где Х вЂ чл Ф' с номером У+ 1. Так как объем )Р равен У+ 1, Х вЂ последн член Ю. Вместе с тем последним членом цепи ТР' является слово 6, так как йг соединяет Р с 6. Поэтому имеем ХИ.6. Таким образом, итерационная цепь 5 алгорифма 4) соединяет слово УРАР со словом ж6. Докажем, что, каково бы ни было натуральное число К, меньшее или равное У, член цепи 5 с номером К+1 имеет вид (У вЂ” К) жХ. где Х вЂ” член цепи (Р" с номером К+1.
При К=О это так ввиду того, что первым членом цепи 5 является слово Уж Р, где Р— первый член цепи Ю'. Пусть теперь К < У, и пусть известно, что член цепи 5 ' с номером К+ 1 имеет вид (У вЂ” К) жХ, где Х вЂ” член цепи )(У с номером К-1-1. Имеем К+2<У+1, и потому имеются член цепи !(Р с номером К+ 2 и член цепи 5 с тем же номером. Пусть г' †чл цепи Ю с номером К+2, Л вЂ чл 5 с номером К -1-2, Тогда Х соседствует слева с 1' в (Р', и потому (25) а(х) ху; (У вЂ” К)РХ соседствует слева с 2 в 5, и потому , (26) 42((У вЂ” К) *Х) Хл.
' Ввиду (25) имеем ,В ((У вЂ” К)*Х) 2г (У вЂ” (К+ 1))*)' Следовательно, Лх(У вЂ” (К+1))ж)' [(26), (27)], , где Я вЂ” член 5 с номером К+2, а г' — член Ю с тем же номером. Пользуясь методом арифметической индукции, мы усматриваем, что при К < У член цепи 5 с номером К+1 имеет вид (У вЂ” К)жХ, где Х вЂ” член цепи )Р' с номе- ром К+1. Поэтому при К < У алгорифм 6 перерабатывает член цепи 5 с номером К+1 в непустое слово [5.2].
Пусть теперь (7 — член 5, не являющийся последним. Существует номер Л4 члена У в цепи 5, меньший объема 5, т. е. меньший У+1. Он положителен и, следовательно, имеет вид К+1, где К вЂ” натуральное число. Имеем К+1 < < У+1, и потому К < У. Таким Образом, (7 есть член цепи 5 с номером К+1, где К < У. Как мы только что видели, отсюда следует, что алгорифм 6 перерабатывает У в непустое слово.
Таким образом, этот алгорифм пере- рабатывает в непустое слово всякий непоследний член цепи 5, соединяющей слово УжР со словом ж 6. При этом Я вЂ” слово в алфавите А и (з(ж 6) л~ Л [5.3]. Согласно построению алгорифма !В мы усматриваем, что (28) ~ (у ж Р) хж6. Кроме того, (29) $(ж6) х6 [5 5] 254 сочетАння нОРмАльных АлГОРнФмОВ 1гл„!ч 255 ПЕРЕВОД АЛГОРНФМА Следовательно, 2)(ыжР)хя [(11), (28), (29)], что и требовалось доказать.
Лемма 5.9 доказана. Вместе с нею доказана и теорема 5.1. $41. Перевод алгорифма Строя нормальные алгорифмы, выполняющие в заданном алфавите ту или иную интересующую нас работу, мы часто бы- ваем вынуждены по ходу дела вводить „дополнительные" бук- вы. Эти буквы отсутствуют в исходных данных и результатах работы алгорифма. Они на время появляются в „текущем" слове процесса и, выполнив определенную вспомогательную работу, перед обрывом процесса исчезают.
Такова, например, буква сс в алгорифме правого присоединения 12 28.3(2)), буквы а, р и у в удваивающем алгорифме (2 31.1(1)) и т. д. Количе- ство дополнительных букв меняется от алгорифма к алгориф- му. Совсем обойтись без них невозможно, как показывает, на- пример, теорема 9 32.3.1. Естественно, однако, спросить, мож- но ли обойтись каким-нибудь фиксированным (желательно, небольшим) количеством дополнительных букв. При естест- венном уточнении этого вопроса ответ на него оказывается ут- вердительным (А.
А. М а р к о в 12), 1П. 2 7.4.2; Н. М. Н а- г о р н ы й Н)). Данный параграф посвящен рассмотрению этого вопроса. Основное содержание его заключено в п. 6. В предшествующих пунктах излагается общая теория перевода слов. 1. Пусть А — алфавит, не содержащий букв а, Ь н Ж. Будем называть А-литероидами буквы алфавита А и слова вида аВа, где  — иепустое слово в однобуквенном алфавите Ь.
Очевидно, что 1.1. Всякий А-литероид есть непустое слово в алфавите Ааь. Легко также показать, что 1.2. Если А-литероид Х входит в А-литероид У,то ХЖ'. В частности, 1.3. Если А-литероид Х начинается или оканчивается А-ли- тероидом 1', то ХоУ. 1.4. Никакой А-литероид не может быть собственным началом или собственным концом другого А-литероида. Ясно также, что !.5. Если Š— А-литероид, а Р— слово в Аа такое, что (Рв)2, то Р не входит в Е. Докажем 1.6.
Всякое вхождение А-литероида Е в слово ВМ5, где — А-литероид, а Е и 5 — слова в АаЬ такие, что 77 не нчивается, а 5 не начинается буквой Ь, имеет один из слева(их трех видов: КМ5, где К вЂ” вхождение Е в В; ВМК, где К вЂ” вхождение Е в 5; йФЕж5, причем Мя Е. В самом деле, пусть 1) ХОСЕФУ вхождение А-литероида Е в слово 14М5, где М вЂ” А-литеоид, а В и 5 — слова в АаЬ, удовлетворяющие перечисленным формулировке леммы требованиям. Тогда Х и У суть слова в АаЬ и выполняется равенство (2) ХЕУхВМ5, В силу (2) слова Х и В суть начала одного и того же слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
