markov_teorija_algorifmov (522344), страница 51
Текст из файла (страница 51)
Пусть Н вЂ” результат действия Р на Р. д (Н) есть результат действия л(Р), т. е. 6, на г(Р). Следовательно, (Н)Х'Х(С7) и Нп 1г [4.21. Таким образом, 9 есть результат действия формулы Р на Р, При этом, как мы видели, Р активна на Р в 5. Следовательно, Й: РГ- Д, что и требовалось доказать. 6.12. Если В: А (Р)) — '.е ф), где Р и Я вЂ сло в алфавите АБ, то Й: Р ) —. (г. Это доказывается аналогично предыдущему. 6.!3.
Й: Р ) тогда и только тогда, когда В: .Х(Р) ) [6.21. 6.14. Если Й: Р'р=Я, то В: '~ (Р) )=Х(Я). Это доказывается методом индукции по шагам работы алгорифма Й с помощью 6,9, 6.16. Если В: 'Х(Р) ) — Х, то существует слово Я в алфавите АБ такое, что Хлел (Я) и Й: Р) — ег. Пусть, в самом деле, В: т (Р) ( — Х. Р является здесь 11 словом в алфавите АБ. Схема 7 действует на слово ~(Р).
Поэтому схема 5 действует на Р [6.21. Обозначим буквой (( результат действия 5 на Р. Имеем Й: Р )-- 1г или Й: Р ',— Однако в случае Й: Р1 — 1) мы имели бы В: .Т,(Р) [ — .Т(Д ) ч [6,101, что несовместимо с нашим исходным предположе- че нием, Таким образом, Й: РР-1е, н потому В: ':(Р)',— е((г) [6.91. Так как при этом В: 'Х(Р) [ — Х, имеем Ха:(Я), что и оставалось доказать. 6.16. Если В: 'Х (Р) ) — ° Х, то существует слово Сг в алфхвите АБ такое, что Х м Х (А7) и Й: Р ) †.
9. Это доказывается аналогично предыдущему. 6.17. Если В: 'Ф(Р),— Х, то существует слово Я в алфавите АБ такое, что Хя. т Я) и Й: Р'=1;1, Это доказывается с помощью высказывания 6.15 методом индукции по шагам работы алгорифма В. 6.18. Если В: А (Р) )= л (ф, то Й: Р'„=(7. Это следует из высказываний 6.17 и 4.2. 6.19. Й: Р~9 тогда и только тогда, когда В: "й (Р),"=3: ((7) [6.14, 6.181. 274 сОчетАниЯ нОРмАльных АлГОРиФмОВ 1гл.
!у 6.20. Й: Р )= 1г ] тогда и только тогда, когда 24: .а(Р))=.А Я) ) [6.19, 6,13]. 6.21. Й: Р ~ .4е тогда и только тогда, когда 6: Й(Р))=.у!. (1г) [6.19, 6.10, 6.12]. 6.22. Й(Р)Х1г тогда и только тогда, когда )В(Ф(Р))ах ль (())[6.20, 6.2Ц. 6.23. Если Р и 43 — слова в алфавите А, то Й(Р)Х1г' тогда и только тогда, когда ьВ(Р) Зй1~ [6.22, 5.15]. 6.24. Если 6: л(Р))= Х, то существует слово 1г в алфавите АБ такое, что Х 313(1г) и й: Р1= 1е. В самом деле„в этом случае существует слово Е в алфавите АаЬ такое, что 4В: 2 (Р);=- )с и что 8: Е ( — Х. Существует слово 6? в алфавите АБ такое, что 7?ХЙ(йУ) и что й: Рр= йу [6.1?].
Имеем дх:;е(%') 1 — Х. Поэтому существует слово 1г в алфавите АБ такое, что Х 31 'л, (1Е) и что Й: йу 1 — !г [6.16]. Имеем й: Р(= 1,1, что и оставалось доказать. 6.25. Если д): А(Р) ~= Х ], то существует слово 1г в алфавите АБ такое, что Х льА(Я) и что й: Р)=(~ [6.17, 6.13]. 6.26. Если Й(хь(Р)) яй Х, то существует слово (г в алфавите АБ такое, что Х Хуь(Я) и что й(Р) 31 1г [6.24, 6.25].
6.27. Алгорифм й тогда и только тогда применим к слову Р в ал4авите А, когда к этому слову применим алгорафм В [6.22, 5.15]. 6.28. Алгорифмы й и дт сильно эквивалентны относительно алфавита А [3 26.6, 6.23, 6.27]. 7. В высказывании 6.28 й и 6 суть нормальные алгорифмы, причем й есть алгорифм в алфавите АБ, а 6 строится определенным образом по данным А, Б и й как нормальный алгорифм в алфавите АаЬ. Относительно букв а и Ь при этом предполагается, что они не входят в алфавит А. Алгорифм дт оказывается сильно эквивалентным алгорифму й относительно алфавита А.
Очевидно, что в этой конструкции буквы а и Ь могут быть заменены любыми двумя различными буквами. Это дает следующую теорему приведения: 7.1. Каков бы ни был нормальный алгорифм й над ал4авитом А и каковы бы ни были отличные друг от друга буквы а и (1, не входящие в А, может быть построен нормальный алгорифм 2) в алфавите Аа(3, сильно эквивалентный алгори4му Й относительно алфавита А, 8. Путем усложнения операции перевода алгорифма одну дополнительную букву в теореме 7.1 можно сэкономить.
Действительно, имеет место следующая у с и л е н н а я 4!1 ПЕРЕВОД АЛГОРИФМА 2?8 т еорем а п риведен и я (см. Н. М. Нагорный [Ц, [2] )): 8.1. Пусть А — непустой алфавит, а а — буква, не принадлежащая А. Всякий нормальный алгори4м й над алфавитом А сильно эквивалентен относительно А некоторому норлсальному алгорифму 9 в Аа. В самом деле, пусть й — нормальный алгорифм в алфавите АБ, где А н Б не имеют общих букв.
Пусть а — буква, не принадлежащая А. Обозначим через ат и Ь; 4-е буквы алфавитов А и Б соответственно н определим следующую операцию перевода алфавита АБ в алфавит Аа: (1<1([А ), (1~1ч '[Б~), [а', = аа!а [ Ьт аа444а с шаха, [Л =Л, К" =[Рт К' (здесь Р обозначает произвольное слово в ЛБ., а $ — произвольную букву этого алфавита). Пусть РР— 6() †форму подстановки в алфавите АБ (здесь 6.а или 63гЛ). Перевод Р определим так: [Р' — [6(гт, если Рф.Л, Грт [аахва- ась!а[61гт, если РаЛ. Построим й — замыкание алгорифма Й. Пусть 1ь. означает схему, получающуюся в результате поформульного перевода схемы алгорифмай.
Определим теперь в алфавите Аа нормальный алгорифм дт следующей сокращенно записанной схемой: аатла$ — [Ет аа,'а 4 4414!к аа,'а [ьт — [Цт аа1а [$4 саха ааяа$ [41' аа,'а — [т)т аасьа аа',ааа',а— — афхаалха, 4) В этих работах утверждение, соответствующее нашей теореме 8.1, формулируется для отношения эхлиеолентности относительно д. Одяако приводимая тэм конструкция фяктияескн годится и для ившнх целей. Мы аоспроиэводнм ее с реобходпмыь~и нэмснеанямн и с небольшим упРощением, 277 ПЕРЕВОД АЛГОРИФМА 276 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ !ГЛ. !Ъ' где переменные С, т! и ~ пробегают алфавиты А, Б и АБ соответственно. Покажем, что алгорифм й сильно эквивалентен В отно- сительно А.
Предполагая, что у читателя накопился необ- ходимый опыт, мы в основном Ограничимся формулиров- ками требующихся здесь лемм и не будем вдаваться в де- тали доказательств. 8.2. Перевод любого непустого слова Р в АБ есть соеди- нение слов вида иая (1(4 <[Аэ) и аа(+'а (!<!<[Ба), и потому слова аа,'и, аа,'а и яа4а в [Р' не входят.
8.3. Первым вхождением аата$ в слово аа,'а[тгтаавис)7 являептся вхождение аата[ЯттхааваЦтх)т (тг, )т — слова в А, 5 — буква этого алфавита). 8.4. Первым вхождением аа',а в слово аа',я [(Етаатва явля- ется вхождение аиста[(гт кап',аз!с Я вЂ” слово в А). 8.5. ПЕРВЫМ ВХОждвпиЕМ аа,'а [Ьт В СЛОЮ аа,'и [тгт аазва[Ь)7т является вхождение аа1и [сг тхаа',а [~т тх [)7т ((Е', ттз — слова в АБ, ~ — буква этого алфавита). 8.6. Первым вхождением [~сааза в слово аа,'а [(гаваи,'а)7 являепия вхождение иаа [!гт тх [Ьт иаа тх тт (ве, й — слова в АБ, ь — буква этого алфавипса). Пусть )с, Т и Š— слова в АБ и Тф'.Л. Образом вхож- дения П Хс Т фЕ будем называть вхождение иова [Авттх [7 т ти [От 8.7.
Непустое слово Т в алфавите АБ тогда и толысо тпогда входит в слово Р в этом алфавите, когда [Т' входит в аа',а [Р, 8.8. Если непустое слово Т входит в слово Р в алфа- вите АБ, то образом первого вхождения Т в Р является первое вхождение [Т в аа,"а[Р', Из рассмотрения схемы алгорифма В следует, что 8.9. Алгорифм В замкнут. 8.10.
В левую часть любой формулы подстановки схемы алгорифма В, кроме последней, входит а. Сформулируем, далее, следующие утверждения: 8.1!. Если Р— слово в А, то В: Р )- аа,'ииа',яР. 8.12. Если Р— слово в А, то В. аазияазир [ иазСС [Рт яавя 8,134 Если Р— слово в А, то В: иа,'я [Ртиавя ) — аа',а [Рт [8.4]. 8.14. Если Р— слово в А, то В. Р~ яавя[Рт [8,11, 8.12, 8.13]. 8.15. Если К и 3 — слова в АБ, то В.
иова[)'лаазя[Ет 'р аазя[)28таава 8.16. Если с) — слово в АБ, К вЂ” слово в А, то В ! аз х [() т [):вт с! Тз с ~ сс тза [(тт иавсс ! т 8.17. Если Я, К вЂ” слова в АБ, Ч вЂ” буква Б, то В: ааза[сгт [т)таа1атс 1 — аа,'а[1!в [т~таазтатс. 8,18. Если с',! — слово в АБ и [Дв',е.Л*), то В (аа',а[Ятаазта) определено и не является словом в А. В свмом деле, пусть выполнено условие леммы. Тогда ЯАГАвт)Е, где т! — буква Б, а Š— слово в А.
Но тогда ССа',а [(Ет иаза .Г ааа [ттт [т)т [От ааа, В; иата фт [т)т [Ет аа',а [= аа,'а [Пт [т)т аазваЕ [8, 16], ) — иова[)7т [т)т аазаЕ [8.17], откуда и вытекает утверждение леммы. 8 19. Если сг — слово в А, то В: яатвииатза(г )-.Я. Сформулируем теперь некоторые леммы, связывающие работу алгорифма В с работой алгорифма й', 8.20. Если й' Р ! — !е, то В: аа,'а[Р')- аазта[сгт. 8.21. Если й': Р Р= !е, то В: аатви[Рт'Р=иатзи[1„'!т [8.20]. 8.22. Если й'; Р )- СЕ, то суи1еспсвуют слова )7 и Е такие, что )752~ Я В: ипата[Р ) — аа,'а [)стаазти[Ет.
8.23. Если й': Р )- сг, то В: аа'а[Р' '~иазти[СЕтаазта [8,22, 8,15]. 8.24. Если й: Р ~- Се, то В: аа',а[Р' [=иота[!!таазта [8,21, 8.23]. 8.25. Если Р— слово в А и й': Р~ Ц, то В: Р)=аа',а[тетяа',а [8,14, 8.24]. ') Капонннаен, что (!се означает проекцию слова !7 на алфавит Б, ПЕРЕВОД АЛГОРИФМА [ГЛ. РЬ СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 8.26. Если Р, Аг — слова в А и й(Р) Х Я, то 9(Р) л'-Ю. В самом деле, пусть выполнены условия леммы. Тогда й': Р ~=.
Аг и, следовательно, В, Р) ааааа'аа]а 'Р= ааваиа,'а Я [8.25] [8.16] [8.19] откуда и вытекает утверждение леммы. 8.27. Если Р— слово в А и алгорифм й применйм к Р, то В также применйм к Р. В самом деле, пусть выполнены условия леммы. Тогда й(Р)ХЦ для некоторого А7 в АБ. Допустим, что слово в Л. Тогда утверждение леммы вытекает из 8.26. Предположим теперь, что Я ие есть слово в А. Тогда [А7е,Ф Л, и так как й': Р)= Я, то 9: Р ~ аа,'а Я'аа',а [8.25]. Но 9(ас4а[(г'аа*,и) определено [8.18], а это означает, что В применйм к Р и в этом случае.
Тем самым лемма 8.27 доказана. 8.28. Если Р— слово в А и В применйм к Р, то й также лрименйм к Р. В самом деле, пусть выполнены условия леммы. Так как В: Р ~ аа',а[Р' [8.14], то В (аа"а [Рх ) и. В (Р) Обозначим через А7 число шагов, за которое В перерабатывает аа',а[Р' в В(Р). В силу леммы 8.20 й' не может совершить, исходя из Р, более )т' простых шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
