markov_teorija_algorifmov (522344), страница 50
Текст из файла (страница 50)
Но, по определению перевода вхождения, Х(Р) есть левое крыло перевода К, а а(Т) — левое крыло перевода Н. Вместе с тем переводы К и Н суть вхождения перевода (~ в перевод 5 [5.1]. Таким образом, перевод К предшествует переводу Н, что и требовалось доказать. Отсюда вытекает 5.11. Если 6 и 5 — слова в алфавите АБ, то разные вхождения !е в 5 имеют разные переводы. Докажем теперь 5.12. Если Я и 5 — слова в алфавип!е АБ, К и Н вЂ” вхождения !е в 5, то перевод К тогда и только тогда предшествует переводу Н, когда К предшествует Н. В самом деле, если К предшествует Н, то перевод К предшествует переводу Н [5.10]. Обратно, пусть й (К) предшествует !Т(Н).
Тогда !Т(К),в Ь(Н), и потому К д. Н. Следовательно, К предшествует Н или Н предшествует К. Однако вторая возможность отпадает, так как тогда !ь(Н) предшествовал бы !ь (К) [5.10] вопреки предположению о том, что й (К) предшествует а (Н). Следовательно, К предшествует Н, что и оставалось доказать. Теоремы 5.1, 5.11 и 5.12 показывают, что при 9 з~.'Л между вхождениями Я в 5 и вхождениями Й(1е) в ! (5) имеется взаимно однозначное соответствие, сохраняющее порядок, Оно сопоставляет всякому вхождению слова 6 в слово 5 перевод этого вхождения. 5.13. Если 5 — слово в алфавите АБ и (г входит в 5, то первое вхождение перевода 1е в перевод 5 есть перевод первого вхождения Я в 5. В самом деле„пусть выполнены условия этой теоремы.
Тогда имеется первое вхождение Я в Я. Обозначим его буквой К и покажем, что перевод К является первым вхождением й(!е) в !(5). Перевод К является вхождением 2(!е) в 3:(5) [5.1]. Если (~хЛ, то 2:(1;!)~Л [4.1], КХяькЯ и переводом К является вхождение !К!К Х (5). Следовательно, перевод К есть первое вхождение $,(!е) в Й(5). Пусть теперь ЯфЛ.
Пусть Н вЂ” какое-нибудь вхождение перевода 6 в перевод, 5, отличное от перевода К. Н есть перевод некоторого вхождения 6 слова 1г в слово 5 (5.7). 6 отлично от К, так как перевод 6 отличен от перевода К. Поэтому, так как К вЂ” первое вхождение !',! в 5, К предшествует 6, а перерод К вЂ” переводу 6 15.10), т. е. Н. Таким образом, перевод К сОчетАниЯ нОРмАльных АлГОРиФмОВ 1гл.
1ч предшествует всякому отличному от К вхождению перевода 1,1 в перевод 5, т. е, перевод К есть первое вхожденяе перевода 1,1 в перевод 5, что и требовалось доказать. 6.14. Пусть 5, 1г и У суть слова в алфавите АБ. Если 1г входит в 5, то перевод результата подстановки У вместо левого вхождения гт 5 гт в 5 совпадает с результатом подстановки Р перевода У вместо первого вхождения перевода (г в перевод 5. В самом деле, пусть (г входит в 5 и К вЂ” перв — ое вхож- . Перевод К есть тогда первое вхождение й(9) вхождение в л. (5) [5.131.
Пусть КХ Р4«(г«Р)х. Тогда перевод К ес есть Ж(Р)ж «(О)мт()7) результат подстановки У вместо К есть слово Р(УР«, а переводом результата подстановки 0 вместо первого вхождения ~~ в 5 является слово $(Р)я(У)А()7), совпадающее с результатом подстановки л. (У) вместо 6.16. то перевода К. . 2:(Р) я. Р для всякого слова Р в алфавите А. Это доказывается методом индукции по построению с помощью 4(2) и 3(2). ро нию слова 6.! . 6. Перевод всякого слова в алфавите АБ ест в алфавите Аад [4.1, 2.8]. фж е АБ есть слово — лфавиты без общих букв, не содержащие звездочки, стрелки и точки. Пусть, кроме того А ыть определена операция перевода л слов в алфавите АБ.
Результатом ее применения к слову Р в ф АБ в алфавите являвербоидом [4.11. «реводю . ( ) слова Р, являющийся некоторым А- Будем называть слово л,(Р) — 7(1г), е Р— , где и †сло фа ите , переводом простой формулы подстановки где Р и — с о Р— 9 в алфавите АБ. Будем называть слово Й (Р) — д (9), (г — л ва в АБ, переводом заключительной фо- 6.1. ии 3 на формулы подстановок.
есть и ос .1. Перевод просп«ойформулы подстанов фав ановки в алфавите АБ закл р тоя формула подспшновки в алфавите АОЬ; ключительной фор чулы подстановки в алфавите АБ есть за; перевод ключительная формула подппановки в ф АаЬ [5. ормула подстановки Р в алфавите АБ тогда и только тогда дейс«пвует на слово Р в алфавите АБ ко да е действует на пеоееод Р 15 8[ ВМ1 ПЕРЕВОД АЛГОРИФМА 271 6.3.
Если формула подстановки Р в алфавите АБ действует на слово Р в этом алфавипы, то перевод результата дейс«пвия . Р на Р есть результат действия т(Р) на А~(Р) [6.2, 5.14), Заменяя в схеме 5 алгорифма 2[ каждую формулу подстановки ее переводом, мы получаем фигуру, являющуюся схемой некоторого нормального алгорифма в алфавите АаЬ [6.1[. Этот однозначно определенный нормальный алгорифм мы будемв,называть переводом нормального алгорифма 61. 6.4. Перевод нормального алгорифма й есть нормальный алгорифм в алфавите АаЬ. Перевод алгорифма 2[ мы будем обозначать буквой 9, его схему — буквой Т.
Между строками схемы 5 и строками схемы Т имеет место очевидное взаимно однозначное соответствие, сохраняющее порядок. Строку схемы Т, соответствующую данной строке С схемы 5, мы будем обозначать знаком С. Имеем, по определению перевода нормального алгорифма, следующие верные высказывания: 6.6. Всякий раз, когда в строке С схемы 5 записана формула подстановки Р, в соответствующей строке С схемы Т записан перевод Р. 6.6. Строка О схемы 5 расположена выше строки С этой схемы тогда и только тогда, когда строка О схемы Т расположена вьиие строки С схемы Т. Докажем высказывание 6.7. Всякий раз, когда формула подстановки Р схемы 5 активна на слове Р в схеме 5, формула подстановки Ф(Р) активна на слове 1ь (Р) в схеме Т.
В самом деле, пусть формула подстановки Р схемы 5 активна на слове Р в схеме 5. Тогда Р действует на Р и имеется строка С схемы 5 такая, что в ней записана формула подстановки Р и что ни в какой выше стоящей строке схемы 5 не записана формула подстановки, действующая на Р. В строке С схе1лы Т записана формула подстановки л.
(Р) схемы Т [6.51, действующая на 7(Р) [6.21. Пусть Е— какая-нибудь строка схемы Т, расположенная в Т выше С. Е соответствует некоторой строке О схемы 5, т. е. Е есть О. В О записана некоторая формула подстановки б схемы 5. В О, т. е, в Е, записана формула подстановки л(б) схемы Т [6.51. Строка О расположена в схеме 5 выше строки С, так как строка Е расположена выше строки С в схеме Т [6.61.
Формула подстановки б схемы 5, записанная в строке О, сочетАния ПОРмАльных АлГОРифмОВ 272 1гл. м не действует на слово Р, так как строка Р, в которой записана формула б, расположена выше С. Поэтому формула е(С) не действует на ~(Р) [6.21. Мы доказали, таким образом, что в каждой строке, расположенной в схеме Т выше С, записана формула подстановки, не действующая на 3(Р). Этим завершено доказательство активности формулы подстановки л(Р) на слове ';ь(Р) в схеме Т.
Докажем 6.8. Всякий раз, когда формула подстановки Р схемы 5 такова, что формула ь (Р) активна на слове ь (Р) в схеме1Т, Р активна на слове Р в схеме 5. (Здесь Р— любое слово в АБ.) В самом деле, пусть Р— слово в алфавите АБ„Р— формула подстановки схемы 5, и пусть формула Т(Р) активна на слове 2 (Р) в схеме Т. Покажем, что Р активна на Рв 5. Так как Т(Р) активна на 2(Р) в схеме Т, Ф(Р) действует на л (Р), и потому Р действует на Р. Имеется строка Е схемы Т такая, что в ней записана формула д,(Р) и что во всякой строке схемы Т, расположенной выше Е, записана формула, не действующая на л (Р).
Строка Е соответствует некоторой строке С схемы 5. Для этой строки С строка Е есть С. Г1усть в какой-нибудь строке Р, расположенной в схеме 5 выше С, записана формула подстановки 6. Тогда в Р записана формула Т(6) [6.51. Строка Р расположена в схеме Т выше строки Е, так как в схеме 5 строка Р расположена выше С [6.61.
Поэтому формула, записанная в строке Р, не действует на . (Р) и потому формула, записанная в строке Р, т. е, 6, не действует на Р [6.21. Мы доказали, таким образом, что во всякой строке, расположенной в схеме 5 выше С, записана формула подстановки, не действующая на Р. Этим завершено доказательство активности формулы Р на слове Р в схеме 5. Тем самым теорема 6.8 доказана. 6.9. Если Й: Р/ — 1г, то В: ~~~(Р) (-2(Я). В самом деле, пусть 91: Р) — 1г. Тогда существует простая формула подстановки Р схемы 5, активная на Р в 5 и такая, что Ц есть результат действия Р на Р.
3 (Р) есть простая формула подстановки схемы Т [6.1), активная на 2(Р) в Т [6.71. а (Сг) есть результат действия Р (Р) на л (Р) [6.31. Поэтому В: д. (Р) г- .'ь ((~). 6.10. Если Й: Р ) —.17, то В: а (Р) ) — ' т М). Это доказывается аналогично предыдущему, 6.11. Если В: й(Р)) — Ж(1г), где Р и ч — слова в алфавите АБ, то Й: Р( — ~ч'. и ПЕРЕВОД ЛЛГОРИФМЛ 273 В самом деле, пусть В: А (Р))- е(е), где Р и ~ч' †сло в алфавите АБ.
Тогда существует простая формула подстановки 0 схемы Т, активная на л. (Р) в Т и такая, что Г(Сс) есть результат действия 6 на Ап(Р). Согласно построению схемы Т формула 6 есть перевод некоторой формулы подстановки Р схемы 5. Р также есть простая формула подстановки [6.Ц. Так как 'Х(Р), т. е. 6, активна на А(Р) в Т, Р активна на Р в 5[6.8). Р действует на Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
