markov_teorija_algorifmov (522344), страница 49
Текст из файла (страница 49)
4.2. Переводы всяких двух различных слов в алфавите АБ различны. Для любого натурального числа У обозначим через ВА. высказывание «каковы бы ни были слова Р и 9 в алфавите ЛБ такие, что [Ра< л( и [(;!а<У, если Й(Р)л.л («г), то Р Х О». Через Вр о обозначим импликацию «если л (Р) Хл ((г), то Рл.!г». Кроме того„ введем условие (5) «[Ра < У и Яа < Л'». Высказывание В» верно, так как при [Ра<0 н [Яа(0 имеем Р»АЛ и !г ХЛ, и потому Рл (Е. Пусть мы уже убедились в истинности высказывания ВА для некоторого натурального числа л!.
Докажем истинность высказывания Вн+1. Пусть слова Р и !г в алфавите АБ удовлетворяют условию (6) «[Ра<А( 1„1 и [()а<А( ! 1 Если эти слова удовлетворяют условию (5), то в силу истинности высказывания В„истинно высказывание Вр „. %«п ПБРБВОД АЛГОРИФМА 263 Допустим, что условие (5) не удовлетворено. Тогда [Р'= = й(+! или [!',!а= У+1. Не ограничивая общности рас- суждения, допустим, что (7) [Ра = )У + 1.
Тогда Р «Л, и потому существуют слово В в алфавите АБ и буква $ алфавита ЛБ такие, что (8) Р»«»»э. Имеем (9) Х(Р) ХЯ;(Р) г($) [(8), (2)), ( РО) [)7а= у [(8), (7)1, (11) 'Т (Р)дЛ [(9)1. Допустим теперь, что (12) 2: (Р) ~ ~ (Я). Тогда л ((2) у. 'Л [(11), (12)1 и потому д ~р Л [(1)). Поэтому существуют слово В в алфавите АБ и буква т, алфавита ЛБ такие, что (1з) 1,! Х Вт1, Имеем (14) х(о) хх(В) ! ® [(13), (2)1. В силу (9), (14) и (12) У(8) и г(Ч) суть концы одного и того же слова. Одно из слов 1(6) и 1(»!) есть поэтому конец другого. Л так как эти слова — Л-литероиды [3.1), они совпадают [1,3). Поэтому (15) « ~ ч [3.21. Имеем (16) $(Р) ( (6) Х»Т(В) ! (»)) [(9), (!4), (12)1, и, так как 1($)Хг(ч), имеем (17) .
л. (!т) ~ 'Т (В) [(16)1. Ввиду (13) и (6) (!8) [В <А, 264 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 1ГЛ. !У Таким образом, соблюдено условие (5) с заменой Р и 1с на В и В соответственно. Ввиду истинности Вн отсюда следует истинность высказывания Вп з. В силу (17) имеем, наконец, (19) П хг Ю и (20) РХ() ~(8), (13), (19), (15)].
Последнее равенство имеет место, коль скоро соблюдено равенство (12). Это означает, что истинна импликация ВР, о. Здесь Р и Я вЂ” любые слова в алфавите АБ, удовлетворя- ющие условию (12) и условию (6). Следовательно, имеет место высказывание Внл н Оно верно, коль скоро верно Вн. Метод арифметической индукции позволяет нам заключить об истинности всякого высказывания В,.
Поэтому равен- ство (20) имеет место для всяких слов Р и Я в алфавите ЛБ, для которых имеет место равенство (12). Следовательно, в случае несоблюдения равенства (20) не соблюдается и равенство (12), т. е. слова Х (Р) и ь(Я) различны, что и требовалось доказать. Равенство, аналогичное (4), имеет место для трех слов: 1 (РЮ) ~ (Р):Ж) Т(Н), где Р, Я и Я вЂ” любые слова в алфавите АБ.
Это равенство очевидным образом доказывается с помощью (4). 5. Как выше, будем предполагать, что звездочка Ф не является буквой алфавита ЛБ. Вхождения в алфавите АБ будем по-прежнему трактовать как слова в алфавите АБтн вида ВхтРФВ, где Р, Р и  — слова в ЛБ. Переводом вхождения РтФРФВ будем называть слово ть (Н) ж Х (Р) Ф Х (В). 5.1. Перевод вхождения слова Р в слово Я есть вхожде- ние перевода слова Р в перевод слова ('1.
В самом деле, пусть Пят Р ФВ, где Н, Р и В суть слова в алфавите АБ, есть вхождение слова Р в слово 1е, Тогда НРВ нтр и потому (1) З:(Н)Х(Р)5(В)~~(® где (Й), 4(Р), (В) и Х(1;1) суть слова в алфавите Лад, не содержащем звездочки. Поэтому '1 (В) ФХ (Р) ЖХ(В) яв- втп ПЕРЕВОД АЛГОРИЬМА 2зз ляется вхождением в алфавите Аад с основой:(Р), т. е. вхождением слова л(Р). л (Н)чти (Р)жл (В) есть вхождение в слово аЯ) ввиду (1). Докажем высказывание 5.2. Всякое вхождение А-литероида в перевод слова в алфавите АБ есть перевод вхождения некоторой буквы ал4авита АБ в слово ~. Доказательство проведем методом индукции по построению слова в алфавите АБ. На время доказательства условимся говорить о слове 1',1 в этом алфавите, что оно правильно, если всякое вхождение А-литероида в Х Я) является переводом вхождения некоторой буквы алфавита АБ в 9.
Требуется доказать, что всякое слово в алфавите АБ правильно. Пустое слово правильно, так как нет вхождений А-литероидов в Х (Л). Пусть для некоторого слова 1е в алфавите АБ выяснено, что оно правильно, и пусть Ч вЂ” буква алфавита АБ. Докажем, что слово ЯЧ также правильно.
Пусть К вЂ” какое-нибудь вхождение А-литероида Ь в а(ЯЧ). Имеем ь%Ч) ~ л %)1(Ч) ~4(2)] где й, ((() — А-вербоид [4.1], ((Ч) — А-литероид 13.1]. Согласно 1.7 имеет место одно из двух: 1'. Имеется вхождение Н А-литероида Ь в слово Х(ф (2) такое, что КХН1(т1). 2'. КХХ(())4тЬФ, причем 1.Хт(т1). В случае 1' Н есть перевод вхождения некоторой буквы $ алфавита АБ в слово 1;1, так как 1„'1 правильно.
В этом случае, следовательно, (3) НХ7(Р) Ф'л (К) ЖХ(В), где слова Н и В таковы, что В Ф $ ж В есть вхождение буквы ~ в слово Я, Имеем ПсВХД, )СьОЧ ~'- ЯЧ и, следовательно, Н Ф з Ф ВЧ есть вхождение буквы в слово ЯЧ. Переводом этого вхождения является слово 2()т') Фа(з) ФХ(ВЧ), т. е. слово К 14(2), (3), (2)].
Таким образом, в случае 1 К является переводом вхождения некоторои буквы алфавита АБ в слово ЯЧ, СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 266 (гл ~г В случае 2' К есть перевод вхождения (ггьг)гь буквы 8 алфавита АБ в слово ггг). Мы доказали таким образом, что слово Яг1 правильно. Итак, коль скоро правильно слово (г, правильно и всякое слово гег1, где г1 — любая буква алфавита АБ. Тем самым высказывание 5.2 доказано. Из 5.2 вытекает 5.8. ВсякийА-литероид, входящий в перевод слова гг, еспгь перевод некоторой буквы слова г",г. Докажем 5.4. Если всякий А-литероид, входящий в А-вербоид еапь перевод буквы алфавита АБ, то гг есть перевод слова в а гфавите АБ.
Будем говорить об А-вербоиде 9, что он правилен, если верна импликация «если всякий А-литероид, входящий в Я, есть перевод буквы алфавита АБ, то Я вЂ” перевод слова в алфавите АБ». Требуется доказать, что всякий А-вербоид правилен. А-вербоид Л правилен в силу 4(1). Пусть Я вЂ” правильный А-вербоид и Š— А-литероид. Докажем, что А-вербоид ггЕ правилен. Допустим, что всякий А-литероид, входящий в ЯЕ, есть перевод некоторой буквы алфавита АБ. Тогда, в частности, всякий А-литероид, входящий в Я, есть перевод буквы алфа- вита АБ. Так как () правильно, г~ есть перевод некоторого слова Р в алфавите АБ: (4) Яха(Р).
Так как А-литероид Е входит в Щ, Е есть перевод некоторой буквы $ алфавита АБ: (5) Е м. т ($). Следовательно, ДЕЛ'~(Р$) [(4), (5), 4(4)~, и мы видим, что ЯЕ есть перевод некоторого слова в алфавите АБ. Этим доказана правильность слова г',гЕ. Применяя метод индукции, заключаем, что всякое слово в алфавите АБ правильно, что и требовалось доказать. Из высказываний 5.3 и 5.4 вытекает 5.5. Для того чтобы А-вербоид (г был периодом слова в алфавите АБ, необходимо и достаточно, чтобы всякий А-литеро- вгп ПЕРЕВОД АЛГОРИФМА 267 'ид,входящий в Я, был переводом некоторой буквы олфави Докажем - ибдь 5.6. Всякий А-вербоид, входящий в период какого-нибу ь .слова в илу ите алфав те АБ, сам есть перевод некоторого слова в алфавите АБ.
В самом деле, пусть А-вербоид гг входит [в ' Р†сло в алфавите АБ. Всякий А-литероид, входящий в гг, входит тогда в л:(Р) и потому является переводом некоторой буквы алфавита АБ [5.31. Отсюда следует, что 4) есть перевод слова в алфавите АБ [5.5], 5.7. Если (е и  †сло в алфавите АБ и Я 7г Л, то всякое вхождение перевода ~ в перевод В есть перевод некоторого вхождения (г в В. Пусть выполнены условия теоремы 5.7. Рассмотрим какое-нибудь вхождение К перевода гг в '~ (В). Пусть Т и У суть соответственно левое и правое крыло К.
Имеем (6) К х Т гк 3 ((~) гк У, л (В) и Х (ге) суть А-вербоиды [4. Ц, причем л (г.г) де Л, так как Я~Л [4.2, 4(1)1. Поэтому Т и У также суть А-вербоиды [2.51. Ввиду (6) имеем 2; (В) Аь Т л (г"г) У, Следовательно, Т и У входят в А-вербоид й(В), а поэтому являются переводами некоторых слов в алфавите АБ [5.61. Пусть (7) Тя.Я:(Р), (8) у х'т(Р), где Р и )7 — слова в алфавите АБ. Имеем К Х й (Р) гК3 Щ ж~(Р) [(6) (7) (8)1 т.
Е. К яВЛяЕтСя ПЕрЕВОдОМ ВХОждсиня РгК9гх)Х И тЕОрЕМа доказана. Докажем 5.8. Если (г и  — слова в алфовсипе АБ, то В. ((с) тог а и только то лько тогда входит в л (В), когда гг входит в В. 3 е им, что при 9я.Л формулировка теоремы 5.8 ста- новитсЯ тРивиальной, так как тогда л'((г)1А [ ( )1г Л 4!1и() входит в В; а лЯ) в гь(В). Пусть теперь (сЕЛ. Если 9 входит в В, то имеется вхождение К слова Я в слово и пер о В и перевод К является вхождением перевода г,г ,л гав'А В), в перевод В [5.Ц.
Следовательно, л (с() входит тогда в ' ( ), т 268 сочетьния ноРИАльных АлгоьиФмов !гл. !ч Обратно, если Х(Я) входит в ь(5), то имеется вхождение Н слова Ж(Я) в слово ь.(5). Н является переводом некоторого вхождения слова ~ в слово 5 [5.7]. Следова.- тельно, !',! входит тогда в 5. Теорема 5.8, таким образом, доказана. Докажем теорему 5.9. Если !е и 5 — слова в АБ, то перевод слова 5 тогда и только тогда начинается переводом слова 6, когда слово 5 начинается словом 6.
Это высказывание также тривиально при 6'и:Л. Пусть 6 ь Л. Если Я начинается словом Я, то имеется слово Н в алфавите АБ такое, что (9) Яхтой. Имеем тогда 1 (5) о ! (а)л ()7) [4 (4)] и, следовательно, слово ь(5) начинается словом ~~ (!',!). С другой стороны, пусть слово 3 (5) начинается словом а (!е). Тогда имеется слово Т [в алфавите Аад такое, что Х (5) х Х Я) Т. Поэтому !к 3 (я) !к Т есть вхождение слова !ь((~) в слово ~ь(5). Так как !е д.Л, это вхождение является переводом некоторого вхождения К слова 6 в слово 5 [5.7]. Переводом левого крыла К является левое крыло вхождения !Р'г(!г)!кТ, т.
е. Л. Отсюда следует, что левое крыло К пусто [4(2)], т. е. что К имеет вид !к!г!Р)с. Так как К вЂ” вхождение !е в 5, имеет место равенство (9), Следовательно, 5 начинается словом !,"г, что и требовалось доказать. Докажем теорему 5.10. Пусть Я и 5 — слова в алфавип!е АБ, К и Н— вхождения !е в 5. Если К предшествует Н, то 3:(К) предшествует Х (Н). Пусть Р и Т вЂ” левые крылья вхождений К и Н соответственно.
Тогда Р есть собственное начало Т, так как К предшествует Н. Поэтому имеется непустое слово Н такое, что (Рд) Т ль РН. Имеем $(Т)ХЙ(Р)Ф(Н) [(10), 4(4)]. 440 ПЕРЕВОД АЛГОРИФМА 269 Здесь ~(Н) ч(-Л, так как )7 ~А [4,2, 4(1)]. Следовательно, л,(Р) есть собственное начало !ь(Т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
