markov_teorija_algorifmov (522344), страница 30
Текст из файла (страница 30)
Пусть и и х — две различные буквы, не входящие в алфавит А. Построим в алфавите Авх нормальный алгорифм ЯА, е „СО СХЕМОЙ хй х х — « где $ пробегает алфавит А. Алгорифм ЯА,, „сокращающий. Поэтому он применим ко всякому слову в Аех. Читатель без труда убедится, что 4.9.
Каковы бы ни были слова Р, Я, Я в алфавите А, алгорифм ЙА, е „перерабатывает слово РЕБР в слово Я. (Сначала е „съедает" Р, затем х „съедает" )с, после этого в и х „уходят" и работа ЙА,, „заканчивается естественным обрывом с результатом Я.) ВВИду 4.9 МЫ НаЗЫВаЕМ аЛГОрифМ ЯА е „ВЫСЕКаЮщиМ алгорифмом для алфавита А. 8 30. Разветвляющий алгорифм 1. Пусть а не является буквой алфавита А. Пусть С, 0 и Š†как-либо фиксированные слова в А. Построим нормальный алгорифм ЯА, с, о е в алфавите Асс«) с сокращенно записанной схемой ( "са- сх$ ас — а а — Е С$ — а | С вЂ” - 11 — а, где с пробегает алфавит А.
Покажем, что он применим ко всякому слову в алфавите А, причем (2) ЙА, с, о, е (С) т«О и (3) «дд, с, о, е(Р) дХЕ для всякого слова Р в А, графически отличного от С. «) Ввиду перехода на нелинейный способ записи схем буквы се, р и у высвобождакпсн, и мы в дальнейшем будем использовать их в качестве букв алфавитов тех илн иных нормальных алгорифмов. 1гл. Рп 154 НОРМАЛЬНЫЕ АЛГОРНФМЫ Чтобы установить (2), мы заметим, что левые части формул подстановок алгорифма ЙА, с, о, е, соответствующие первым пяти строкам схемы (1), в С не входят, так как зти левые части либо содержат букву а„либо имеют длину, на единицу ббльшую длины слова С. Левая часть следующей формулы подстановки С вЂ” Р входит вС.
Таким образом, эта формула активна на слове С в схеме (1) и результат ее действия — а тем самым и результат действия схемы (1) — на слово С, как легко видеть, есть слово Р, и так как в данном случае активная формула подстановки является заключительной, то ЙА, с, о, е' .С) откуда непосредственно следует (2). Для установления истинности утверждения (3) мы докажем следующие восемь лемм 1.! — 1.8.
В них Р, Я и )« будут обозначать произвольные слова в алфавите А, а $— любую букву этого алфавита. 1.1. ЙА. с. о, е. 'ЯаЯ [ — (га$)«. В самом деле, на слово ДаЯ действует в точности одна из формул подстановок, представленных первой строкой схемы (1): формула $а — а$.
Именно она и является в данном случае активной. Вхождение Я»»$атй является единственным — а следовательно, и первым — вхождением ее левой части в слово (Ка)с. Значит, результат действия схемы (1) на слово Яа)«есть (4аЯ. А так как активная формула простая, то ЙА, с. о, е: «4с«»м г Ф»ап что и требовалось доказать. Таким образом, лемма 1.1 говорит о том, что в результате одного простого шага буква а в слове вида Яа)с „продвигается" на одно место влево. 1.2. ЙА, с, о, е. 1,Ахгг')=с»Я)7.
Это утверждение мы докажем правой индукцией по Д. Для этого мы рассмотрим свойство Р слова Я, выражаемое условием «каково бы ни было )«, ЙА, с, о, е' Яа)«)=абай», и покажем, что любое 9 обладает этим свойством. В самом деле, пустое слово обладает свойством Р [3 25,6. Ц.
Пусть теперь Я обладает Р, а $ — какая-либо буква. Тогда (4) ЙА, с, о, е: Я«»)7 [ — Я«««ьй [1. Ц. 4 »О> РАзветвляющин АЛГОРИФм ь' Но $)7 — слово в А, и потому по индукционному предположению (5) ЙА, с, о. е: Яс«4Й )= ««Я)с. 'ьл следовательно ЙА, с, о, е.' Яа)7)=аЯК [(4), (5), й 25.6.2, й 25,6,3] и, значит, Я обладает свойством Р. Таким образом, действительно, любое 9 обладает свойством Р, а это и доказывает наше утверждение. 1.3.
ЙА, с, о, е'. а5Р) — аР. В самом деле, ни одна из формул подстановок, представленных первой строкой схемы (1), не действует на АР. Вхождение тай«« 9 есть единственное вхождение слова вида а$ в а$Р. Таким образом, из рассмотрения схемы (1) вытекает, что формула а$ — а является активной на ааР в схеме (1), и потому ЙА, с, о, е' а$Р1-,аР, что и требовалось доказать. 14.
ЙА,с, о,е: иР~=а, Докажем это утверждение левой индукцией по Р [~ 17.3.2]. Для этого рассмотрим свойство б слова Р, выражаемое условием «ЙА. с, о, е. 'аР )=а», и покажем, что этим свойством обладает любое слово Р. Действительно, пустое слово им обладает [$ 25.6. Ц. Пусть теперь Р обладает б, а $ — какая-либо буква. Тогда (6) ЙА, с, о, е: аэР) — аР [1,3]. Но по индукционному предположению (7) ЙА, с. о, е: ««Р ~= а, и потому ЙА, с. о, е. азР1=а [(6), (7)], т. е. КР обладает свойством О. Значит, любое Р обладает этим свойством, а это и требовалось доказать.
1.5. ЙА, с, о.е' с»1 — Е. В самом деле, формулы подстановок, представленные первыми двумя строками схемы (1), не действуют на а, а формула а Е действует на это слово и, значит, она является и данном случае активной. Вхождение осок НОРМАЛЬНЫЕ АЛГОРИФМЫ 1гл, ги является первым вхождением левой части этой формулы велозо а. Результат подстановки ее правой части вместо этого вхождения есть Е, и так как эта формула является заключительной, то ЙА,с,о,е ° а) — Е, что и требовалось доказать. 1.6. Если С входит в Р и Р 1!'С, то существу!От такие слова !г и )7 в А, что йА, с, о. А! Р1-!еа)7.
В самом деле, пусть Р— слово в А, отличное от С, и пусть С входит в Р. Тогда в Р входит либо одно из слов вида Сс, либо одно из слов вида $С. Иначе говоря, в Р входит левая часть хотя бы одной из формул, представленных четвертой и пятой строками схемы (1). Левые же части выше стоящих формул, содержащие а, не входят в Р. Поэтому на Р активна одна из формул, представленных четвертой или пятой строками схемы (1). Эта формула имеет вид 5- а, и требуется применить ее к первому вхождению слова 5 (равного С$ или сС) в Р. Пусть Я:ЮЮ будет этим вхождением.
ТОГда !Е и )С сУть, как и Р, слова в А, а результат подстановки правой части формулы есть слово 1",чхЯ. Так как активная формула простая, ЙА, с, о, е' Р) — ЯсеЯ, что и требовалось доказать. 1.7, Если С не входит в слово Р в алфавите А, то ЙА.с, о, е' Р) — аР. В самом деле, в этом случае из левых частей формул подстановок алгорифма ЙА, с, о, е левая часть последней формулы — пустое слово — входит в Р, все же остальные не входят в Р, так как в них входит либо а, либо С. Следовательно, требуется подставить правую часть последней формулы,т. е.
а, вместо первого вхождения пустого слова в Р, что дает иР. Так как активная формула простая, то ЙА с а, е. Р )- гАР, что и требовалось доказать. 1.8, Если Р— слово в алфавите А, отличное от С, то могут быть указаны такие слова Д и Я в А, что ЙА, с, о, е: Р~ — Фх)7. В самом деле, если С входит в Р, то такие Я и Д могут быть указаны согласно 1.6. Если же С не входит в Р, то, согласно 1.7, в качестве Я можно взять Л, а в качестве )7 слово Р.
Мы можем теперь доказать равенство (3). В самом деле, пусть Р— слово в А, Отличное от С. Возьмем слова Я и взп УДВАИВАЮЩИИ АЛГОРИФМ 167 Я в А согласно 1.8 таким образом, что ЙА, с. о. е: Р1-Яа)7. Имеем тогда ЙА. с, о, е! 'Р1 — (еа)7 )=а4)7 [1,21 )=а [1.41 ) — Е [1,5], :; Откудайм с. о. е! Р~ е, и потому ЙА с р е(Р) ~е [~25 7~ .' что и требовалось доказать. Таким образом, работа алгорифма ЙА, с, о е над словом Р вА протекает следующим образом. Если Р Л.С, то ЙА, с, о, е за один шаг переводит Р в Р и на этом его работа закан- чиваетсЯ.
Если же Р:ГС, то ЙА, с, о,е „ввоДит" в пеРеРабатываемое слово сигнализирующую об этом букву а [1.81, 1 которая „выходит" затем в начало слова [1.21, „стирает" его [!.41 и „превращается" в Е [1.51, после чего работа .. ЙА, с, о, е прекращается. 8 31. Удваивающий алгорнфм 1. Пусть а, р и у означают различные буквы, не принадлежащие алфавиту А. Построим нормальный алгоритм 5А в алфавите Аару с сокращенно записанной схемой чав — срч а$ — $Яа — 7 7 где $ и !) пробегают алфавит А (при н-буквенном алфавите А эта схема состоит из л'+и+4 формул подстановок).
Покажем, что (2) 5А (Р) й. РР для всякого слова Р в А. Для установления истинности утверждения (2) мы введем две операции Ф и Ч" над словами в А, а затем докажем леммы 1.1 — 1.14, из которых это утверждение будет вытекать. В даль- нейшем Р, !Е, К„Я будут обозначать произвольные слова в А, а а, т1 — любые буквы этого алфавита. (Гл. «и 158 П (3) (4) (5) (6) НОРМАЛЬНЫЕ АЛГОРИФМЫ замечание в 3 17.3.2) Ф(Л) Л, Ф (Рз) — Ф (Р) х(6, Ч'(Л) — Л, Ч'(Р$) Ч'(Р) $7. $А: Р1-аР, что и требовалось доказать.
1.2. $А. Яа)- ° Я, Доказывается аналогично 1.1 рассмотрением схемы (1). Формулой подстановки, активной в (1) на Яс«, является формула а- 1.3. 5А. 'Ф (Р) Ра$Я 1- Ф (Р) Р$ЯаЯ. Доказывается рассмотрением схемы (1). Легко видеть, что ни одна из формул, представленных первой строкой схемы (!), не действует на слово Ф(Р)Ра$Я. Между тем среди формул, представленных второй строкой, имеется формула а$-~-$Яа с левой частью, входящей в Ф (Р)Ра$Я. Эта формула и является активной на данном слове.
Единственное вхождение ее левой части в рассматриваемое слово имеет внд Ф (Р)РФа$Х«Я. Вместо него подставляется правая часть формулы, т. е. слово $Яа, Легко видеть, что (7) Ф ($) Х ф 1(4), (3)], (8) Ч'($) х $7 ~(6), (5)]. Кроме того, правой индукцией по Я нетрудно показать, что (й) Ф (Р!~) Аь Ф (Р) Ф (1~) !(3), (4)] и (1О) Ч,(Р® х Ч (Р) Ч (О) 1(6), (6)]. Имеем 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
