markov_teorija_algorifmov (522344), страница 45
Текст из файла (страница 45)
Так как )Р' начинается и оканчива- ется буквой у, яг есть у-система в алфавите А(). Так как Т начинается и оканчивается буквой у, Р есть первый, а ()4е— последний член )Р', т. е. %' соединяет Р с К. Так как Т содержит у, )Р' многочленна. Покажем, что (Р' есть итера- ционная цепь алгорифма Й. Пусть Х соседствует с У слева в Ф'.
Имеет место одно из двух: а) Хесть последний член у-системы уРТ, а 1' я.р4г; б) Х соседствует слева с )' в уРТ. Рассмотрим эти два случая. а) В этом случае Х соседствует слева с (г в О 1(26)], и так как О' есть итерационная цепь алгорифма й, то (28) й(Х) Х(1, Х есть слово в алфавите А. В силу того, что 6(4Е)я.Л, имеем (29) 6 Я) К Р'].
Следовательно, Ж(Х) ~6() 1(28), (29), (23)], т. е. (зо) й(Х)ХЬ . б) В этом случае Х соседствует слева с 1' в Я и потому (31) й (Х) хг У. У вЂ” член Т, и потому 1' — внутренний член Ю [(26)]. Следовательно, алгорифм 6 перерабатывает 1' в непустое слово. При этом 1' есть слово в алфавите А 1(31)]. Поэтому (32) ~(у)ху 13]; равенство (30) имеет место и в данном случае 1(31), (32), (23)]. 24О сочетлння НОРМАльных Алгогиамоа [гл. !ч Таким образом, (р' есть итерационная цепь алгорифма З, По буквой 13. кажем, что никакой внутренний член )р' не начн нается Пусть г' †внутренн член Ю, Тогда 1' есть член Т [(27)1, н потому, так как Т есть 7-система в А, 1' есть слово в А.
Следовательно, 1' не начинается буквой р. И так, ну есть многочленная итерационная цепь алго- рифма Ж, соединяющая слово Р в алфавите А со словом Я в алфавите А() и такая, что никакой ее внутренний член не начинается буквой )1. Р является при этом словом в алфавите Д, содержащем алфавит А [(23)1; буква [1 также входит в Д и слово Щ есть слово в алфавите Д, а значит, и в алфавите алгорифма й; слово Я начинается буквой 15, Согласно построению алгорифма (11 заключаем, что имеет место равенство (33) Е (Р) ~Я Согласно схеме алгорифма 6 имеем (34) 6(р®яЯ Поэтому выполняется равенство 6(Р)~ьО [(ЗЗ) (34), (25)3 что н требовалось доказать. 3.17.
Если Х вЂ” слово в алфавите А, 'л1 (Х) Х 1' и слово 1' не начинается буквой р, то )' есть слово в алфавите А, Л (Х) Х 1' и 6 перерабатывает 1' в непустое слово. В самом деле, при соблюдении условий этой леммы имеется слово л в алфавите А таков, что (35) 47((Х) х2 и (36) 4у (4.) Х 1' [(23)1, 5 применйм к 2 [(36)1, и потому 6 применйм к 2 [1'), т.
е. имеется слово У такое, что 6(2) ХУ. Если бы слово 1l было пустым, то мы имели бы (37) 6 (2) ~2 [2'1, начинается откуда )'Щ2 [(35), (37)), что невозможно, так так как не тся буквой 1ь. Следовательно, Уль.'.Л, и потому (38) Р)(2) лг г [3') откуда (39) 1'лг2 4 401 ПОВТОРЕНИЕ АЛГОРИФМА 241 [(35), (38)1. Таким образом, У есть слово в алфавите А и ьг((Х) х У [(35), (39)1, что и требовалось доказать. 3.18. Если Х вЂ” слово в алфавите А и л)(Х) Р рГ, то 1' есть слово в алфавите А, е( (Х) льУ и 6(1 ) л.Л.
В самом деле, при соблюдении условий этой леммы суествует слово 2 в алфавите А такое, что имеет место (35) и что 40) Я (2) х Я' [(23)). 4т применйм к л, и потому 6 применйм к 2 [1'1, т.е. , существует слово У такое, что 6(2)яУ. Если бы У было непустым, то мы имели бы (41) 0 (2) Х2 [3'1, откуда 2л.р1' [(40), (41)), что невозможно, так как Е— слово в алфавите А, не содержащем р. Следовательно, УХЛ и 6(2) дЛ, в силу чего (42) 6 (2) х Рг [2'1. Поэтому р)'я.()2 [(40), (42)] и, значит, Ум#.
Таким образом, 1' есть слово в алфавите А, й (Х) Р У[(35)|и 6(У) мЛ, что и требовалось доказать. 3.19. Если имеет место равенство З(Р) ХЯ, где Р в А, то 1е — слово в алфавите л, 6((г) мл и существует многочленная итерационная цепь 5 алгорифма 2(, соединяющая Р с 11 и такая, что 6 перерабатывает в непустое слово вся'. кий внутренний член Я. В самом деле, пусть соблюдено условие леммы. Тогда существует слово )7 такое, что 7с (43) 9 (Р) Хй и (44) 6 ()7) мь',1 р [(25)1.
Согласно построению нормального алгорифма Ю, )7— слово в Д, начинающееся буквой р, и существует многочленная итерационная цепь )Р' алгорифма ц1, соединяющая Р с )А' и такая, что никакой ее внутренний член не начинается буквой (). ))г есть у-система в алфавите Д алгорифма 2. Ввиду многочленности ЯГ существует у-система Т в алфавите Д такая, что (45) Ф'7АТРТКТ. 242 сочетхния ноРмхльных АлгогиФмов [гл, ш Система Т есть итерационная цепь алгорифма д) [2,11. Ввиду (44) )с есть слово в алфавите Ар алгорифма Ю. Вви- ду того, что )с начинается буквой р, существует слово и в алфавите Ар такое, что (48) л 3:би. Ясно, что всякий член у-системы Т есть внутренний член йГ и, следовательно, не начинается буквой Р. Докажем, что всякий член Т является словом в алфавите А и что алго- рифм 6 перерабатывает всякий член Т в непустое слово.
Это верно, когда Тя.у, так как в этом случае не сущест- вует членов Т [2 91, Пусть Т.,Р у. Тогда имеется единствен- ный первый член У системы Т. У есть также первый член у-системы Тйу, Поэтому Р соседствует слева с У в йГ. Так как )У вЂ” итерационная цепь алгорифма 2, (47) 2(Р) х У. Здесь Р— слово в алфавите А, а У не начинается буквой р. Поэтому 1' есть слово в алфавите А и 6 перерабатывает 1' в непустое слово [3.171.
Пусть теперь Х есть слово в алфавите А, пусть 6 пере- рабатывает Х в непустое слово, и пусть Х соседствует слева с 1' в Т. Тогда 1', как член Т, не начинается буквой р и Х соседствует слева с У в йГ, ввиду чего (48) З(Х)~У, Поэтому 1' есть слово в А и 6 перерабатывает У в непус- тое слово [3.171, Применяя метод индукции по построению системы, за- ключаем, что всякий член Т есть слово в алфавите А и что алгорифм 6 перерабатывает всякий член Т в непустое слово.
Таким образом, Т есть у-система в алфавите А, Покажем, что Т есть итерационная цепь алгорифма 2(. В самом деле, пусть Х соседствует слева с У в Т. Тог- да Х соседствует слева с У в В' [(47)), ввиду чего имеем (48), Здесь Х и У вЂ чле Т и, значит, слова в алфавите А. 1' не начинается буквой р. Поэтому (49) Я (Х) '~ У [3.171. Положим теперь (50) 3= ТРТау. Здесь Р— слово в А, Т вЂ” у-система в А, Я вЂ” слово в алфа- вите А() алгорифма 6 [(44)1. Поэтому 3 есть у-система в 2 441 повтонвнив АлгогиФЯА 243 алфавите Ар [(50)1, Покажем, что 3 есть итерационная цепь алгорифма л.
Пусть Х соседствует слева с 1' в Б. Тогда имеет место дно из четырех: 1'. Х хР 1' — первый член Т 2'. Х соседствует слева с У в Т. 3'. Х вЂ последн член Т, Уя.(), 4'. Х Х Р, 1' Х Я, Т Х у. При осуществлении п. 1' Х соседствует слева с У в й7, и потому имеем (48). При этом Х вЂ” слово в алфавите А и слово У, как член Т, не начинается буквой р. Поэтому ' имеем (49) [3.17].
Прн осуществлении п.2' также имеем (49), так как Т, как мы видели, есть итерационная цепь алгорифма Й. Допустим, что осуществляется п. 3'. Тогда Х соседствует слева с )х в ИГ (45), и потому (51) З(Х)ХР, т. е. (52) ь (х) х би [(48)1, ' откуда ; (53) 8((х) х и [3.18), т. е. (49), так как, согласно схеме 6, (44) и (48), имеем и х я. Пусть, наконец, осуществляется п. 4'. Тогда йг ~ ТР77(у, где Р и )с суть слова в алфавите Ар. Следовательно, Р соседствует с Р в НГ, и потому имеем (51), т. е.
(52). Отсюда, как выше, получаем (53), т. е. (49). Этим завершено доказательство того, что 3 есть итерационная цепь алгорифма Й. Таким образом, 9 есть слово в алфавите А. Покажем, что 6 (Я) Х Л . Возможны два случая: Тд у и ТХу. В первом случае пусть У вЂ” последний член Т. Тогда У соседствует слева с 9 в 3 и, полагая Х=У, У Я, имеем для Х и У п.3', рассмотренный выше.
Как мы видели, : тогда имеет место равенство (52), откуда с учетом равен- : ства и э Я следует„что 6Я) я. Л [3,181, Во втором случае, полагая ХмР и У=~',1, имеем для Х и У п. 4'. Тогда также осуществляется (52), откуда снова 6 ф) х Л. 244 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ [ГЛ. !Ч Итак, Я вЂ” итерационная цепь алгорифма Я. Она соединяет Р с Я и многочленна. Всякий внутренний член 3 является членом Т, и поэтому алгорифм 6 перерабатывает в 6(ф А[Л. непустое слово всякий внутренний член 3.
Након ц, е, имеем Лемма 3.19, таким образом, доказана. Из лемм 3.16 и 3.19 вытекает лемма 3.20. Равенс[лво 6(Р) лгЯ, где Р— какое-нибудь слово в алфавите А, имеет место тогда и только тогда, д ког а ([Е) и существует многочленная итерационная цепь 3 алгорифма Я, соединяющая Р с [г и пиная, чт 6 я, что лерера атывает в непустое слово всякий внутренний член 8. 3 Й десь Й и С вЂ” любые норл[альные алгорифмы в а ф лфави, а †нормальн алгорифм, построенный с помощью Я и 6, как описано выше.
Тем самым теорема 3.1 доказана при условии, что Й и 6 суть нормальные алгорифмы в одном и том же алфавите. Чтобы доказать теорему о повторении в общем случае, можно воспользоваться уже неоднократно примененным приемом перехода к формальным распрост анениям рассматриваемых нормальных алгорифмов, Подробное доказательство предоставляется читателю. Результирующий нормальный алгорифм [О мы будем называть нормальным повторением алгорифма Й, уп авляемым алгорифмом 6. ,оавляеМы будем обозначать этот алгорифм посредством (Я('.) 6). Отм тметим два простых, но важных следствия теоремы 3.1. 3.21.
Если 6(Й(Р))дЛ, то (Й~)6) (Р) ХЯ(Р). В самом деле, пусть 6(Й(Р))мЛ. Тогда Й(Р) осмыслено. Положим З= ТРТЙ (Р) у. Как легко видеть, у-система 5 соединяет Р с Й(Р) и является итерационной цепью алгорифма Я. Действительно, Р является первым членом 3, а Й (Р) — ее последним членом. Кроме того, если Х соседствует слева с 1' в 5, то Х м Р и Г' д[Я(Р, ( ), и потому Я (Х) л К. Итерационная цепь 5 является многочленной, так как 15' = 2. Все ее внутр члены (их попросту нет) алгорифм 6 перепабатывает в не- внутренние пустое слово 12 9].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
