markov_teorija_algorifmov (522344), страница 36
Текст из файла (страница 36)
в Тогда (10) (11) ~ ~5йги [(9)], ~)7 — 5пРц)Р [(10)]. Таким образом, 1е)7 есть результат подстановки В' вместо 5 к-Т м-(7)7 [(11)], т. е. вместо образа У[(9)], что и требовалось доказать, 2.7. Если й: Р ) — (), то 6: Рй 1 — Щ. В самом деле, пусть й: Р )- Я. Пусть Р— формула, активная на Р в схеме й.
Левые части формул, предшествующих Р в схеме й, не входят в Р, а значит, и в РК, так как они являются словами в А [2,5]. Левая же часть Р входит в РК, так как она входит в Р. Ввиду совпадения схем алгорифмов Й и 6, Р является, таким образом, формулой схемы В, активной на слове РК. Пусть У вЂ” первое вхождение левой части Р в Р. Тогда образ У есть первое вхождение левой части Р в РК [2.4].
Алгорифм В в применении к слову РК предписывает поэтому подставить правую часть формулы Р вместо образа У. Но результатом подстановки правой части Р вместо У является слово Я, так как й: Р ~- 9. Следовательно, результатом подстановки правой части Р вместо образа У является 11)~ [2,6]. При этом формула Р простая, так как Й: Р)- Я. Следовательно, В: РР. )- 1е1(, что и требовалось доказать. 2.8. Если Й: Р 1- ° Я, то 6: РК ~- Щ. Это доказывается совершенно аналогично предыдущему. 2.9.
Если Й: Р ], лто 6; РК 1. Это легко доказывается с помощью 2.5. До сих пор слова Р и )7 были у нас закреплены, что имело существенное значение при определении образа вхождения. В доказанных леммах 2.7 — 2.9 понятие образа вхождения, однако, не фигурирует. Эти леммы применимы поэтому к любым словам Р, (е, )7 таким, что Р есть слово в А, а )т — в Б",А. В дальнейшем оии и будут применяться таким образом. В леммах 2.10 — 2.20 мы также предполагаем, что Р есть слово в А, Р— в Б",А.
2.10. Если 6: РК) — 5, то существует такое слово 11 в А, юлс 5м(ЕТТ и й: Р 1 — 1'1. бб1 РАСПРОСТРАНЕНИЯ АЛГОРИФМА 191 В самом деле, пусть В: РК 1 — 5. Имеет место одно из ьледующих трех утверждений: или существует такое слово Ч1, что Й: Р )-1,1, нли существует такое слово (Е, что й: Р )- ° 1~, или Й: Р ] [~ 25.4.7].
Во втором слу,чае мы имеем, однако, В: РК) — 1~)7 [2.8], в третьем— АВ Рй'] [2.9]. Так как ни то, ни другое не совместимо ! с предположением, что В: Р)«)- 5, эти случаи отпадают. .)[1Таким образом, существует такое слово 1Е, что й: Р) — Я. ,ф есть слово в А, так как Й вЂ” нормальный алгорифм в А. „'Так как й: Р )- 1е, имеем В: Рй ) — Я)г [2.7]. А так как, по :предположению, В: РК)-5, то 51А1Я, что н оставалось ', доказать. Аналогичным образом доказываются следующие две ' леммы: 2.11. Если 6: РТТ)-.5, то существует такое слово 1',1 в А, что 5 м 1'1)7 и й: Р 1- 1Е.
2.!2. Если 6: Р)г], то Й: Р ]. Докажем 2.13. Если Й: Р)=(е, то В: Ргт* ~= Я)7. Это утверждение легко доказывается — с использованием леммы 2.7 — методом индукции по шагам работы алгорифма й [25.10]. Ввиду типичности этого рассуждения мы для первого раза проведем его, несмотря на всю простоту ситуации, с максимальной тщательностью. Итак, рассмотрим, зафиксировав Р и 1«, свойство Р слов ,'1~ в алфавите А, выражаемое условием «В: Рб«)=Е7>, Наша задача заключается в том, чтобы показать, что, во-первых, Р обладает свойством Р и что, во-вторых, для любых и 5 таких, что Й: Р)= 1~ )-5, из наличия свойства Р у 1~ , вытекает наличие его у 5. Покажем это. Слово Р обладает свойством Р тривиальным образом «' [9 25.6.1].
Пусть теперь 17 и 5 — слова такие, что Й: Р Ь= (~ 'й и й: (1 1- 5, и пусть В: РК )= 1~)7. Покажем, что В: РК )= 5)7, :: Но это действительно так, потому что из й: Я 1 — 5 следует В: ф7)-5К 1'2.7], а это в сочетании с В: РР)=«Е)г дает В; РЯ ~-5Р Ц 25.6.2, $ 25.6.3]. Таким образом, оба условия применимости метода индукции в нашем случае выполнены. Заключение индукции в рассматриваемой ситуации утверждает, что при фиксиро, ванных Р и А' импликация 2.13 верна для любого Я, Но " Р и )7 были фиксированы произвольно, так что 2.13 имеет место прн любых Р, 1е и 77, что и требовалось доказать. 2.14. если Й: Р)== 1е, то В; РР)='1',1)т.
с92 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ сГЛ. ст В самом деле, пусть й: Р )= !с. Тогда существует 3 та кое, что й: Р~=З и Й: Я! — ° ьс. но тогда 6: Р!«)=зсмк [2.13] и 6: О)с!- ф7 [2.8], откуда 6: Рс«'Р= Щ, что и требовалось доказать. 2.18. Если й: Р)=(с' ], то 6: Р)7~=се!к' ]. В самом деле, пусть Й: Р)=с~ !. Это значит, что й: Р ~= Я и й: Я ]. Но тогда 6: Р)т )=(е)т [2.13] и 6: Щ ] [2.9], следовательно, 6: Р!7 )= ф7 ], что и требовалось доказать. 2.16. Если 6: Рс« ~5, то существует слово Т такое, что ЗхТЕ и й: Р)=Т.
Зафиксируем Р и 1« и докажем это утверждение методом индукции по шагам работы алгорифма 6. С этой целью рассмотрим свойство Р слов 3 в алфавите А, выражаемое условием (12) «существует слово Т в А такое, что ЯХТА и Й: Р1=Тв. Покажем, что всякое слово 3 такое, что 6: Р1«)=З, обладает этим свойством. В самом деле, слово Рс« обладает свойством Р, так как в качестве Т в (12) можно взять Р. Пусть теперь 3 и !с таковы, что (!3) 6: Р)7~=3!- д и 3 обладает свойством Р. Покажем, что тогда им обладает и С~. Действительно, существует Т такое, что О'м. ТР и й: Р~ Т. Но тогда существует У такое, что 9ХУ)7 и й: Т 1- У [(13), 2.10].
Следовательно, С',!АУ)7 и й: Р )= У. Тем самым лемма 2,16 доказана. 2.17. Если 6: Ргс )= 3, то алгорифм й применйм к Р. В самом деле, пусть 6: Рсс ~= 3. Тогда существует слово Т такое, что 6: Рст '5=Т с- 3. Но тогда существует слово У такое, что ТХУ)т и й: Р)=У [2.16]. Если бы существовало слово )с такое, что й: У ! — )с, то было бы 6: Ус« 1- 'Р')Ас [ .7], что противоречит 6: Ус« 1- 3. Аналогично, невоз- 2. можно Й: У ! [2.9].
Следовательно, для некоторого !Р' имеет место й: У 1- ° Ж'. Но тогда й: Р~=.97, и, значит, 1Й (Р), что и требовалось доказать. Аналогичным образом доказывается и следующая лемма: 2.18. Если 6: Рсс)=Я ], то алгорифм Й применйм к Р. Докажем теперь 2.19. Если алгорифм Й применйм к Р, то 6 (РР) Х Й (Р) )7. 7 «зм РАСПРОСТРАНЕНИ55 АЛГОРИФМА Гээ Допустим, в самом деле, что алгорифм й применим к Р, - и пусть имеет место равенство с (14) Й (Р) Х Я. Тогда й: Рс= Сг' или Й: Р,=(С ].
В первом случае 6; РК)= 977 [2.14], во втором 6: Р(7,'= Е7 ] [2.15]. В обоих случаях 6 (РК) Р 67 я й (Р) Р, что и требовалось доказать. 2.20. Если алгсрифм 6 применим к Рс«, то алгорифм Й применим к Р. В самом деле, если алгорифм Ю применим к Рй, то существует такое слово 3, что 6: РК )= 3 или 6: Рсх )= 3 1. В обоих случаях алгорифм Й применим к Р [2.17, 2.18], что и требовалось доказать. Из лемм 2.19 и 2.20 непосредственно следует интересующий нас результат, а именно условное равенство (1).
Из него вытекает условное равенство 1(1). Этим доказано, что 6 есть распространение Й на Б. 3. Распространение нормального алгорифма Й на алфавит Б, получаемое как только что указано, мы будем называть естественным распространением этого алгорифма на алфавит Б.
Предыдущее мы резюмируем следующим образом: 3.1. Естественное распространение нормального алгорифма есть нормальный алгорифм. 3.2. Схема естественного распространения нормального алгорифма совпадает со схемой этого алгорифма. З.З. Каковы бьс ни были нормальньсй алгорифм Я в алфавите А и расисирение Б этого алфавита, существует естественное распространение алгорифма Й на алфавит Б. 3.4.
Если 6 — естественное распространение на алфавит Б нормального алгорифма Й в алфавите А„то имеет место условное равенство 2(1). 4. Пусть Я вЂ” нормальный алгорифм в алфавите А. Если Б — собственное расширение этого алфавита, то естественное распространение алгорифма Й на алфавит Б может оказаться применимым не только к словам в алфавите А. Оно будет, например, применимо и ко всякому слову в Б' А, если схема алгорифма Й не содержит формул подстановок с пустой левой частью.
А. А. Мврквв, Н. М. Нввврвва !94 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ !ГЛ. !Р В самом деле, в этом случае левые части всех формул подстановок алгорифма й суть непустые слова в алфавите А и, как таковые, не входят в слово в алфавите Б",А. В силу совпадения схем алгорифма й и его естественного распространения 5 на алфавит Б это означает, что .'В: Р ! для любого слова Р в Б' А. Отсюда следует, однако, что л) (Р) м Р для всякого такого слова Р. В некоторых случаях оказывается желательным так по- строить нормальный алгорнфм в алфавите Б, чтобы он был распространением алгорифма й на этот алфавит и чтобы вместе с тем ои был применим только к словам в алфавите А (и, значит, к тем и только тем словам, к которым при- меним й).
Это достигается следующим образом. Присоединим к схеме алгорифмай сверху всевозможные формулы вида (1) $ $, где $ — произвольная буква алфавита Б;,А. Зададим нор- мальный алгорифм 6 в Б схемой, получаемой таким обра- зом. Тогда, как нетрудно видеть, б также есть распрост- ранение й на Б. В самом деле, присоединение формул вида (!), очевидно, никак не отразится на первом шаге применения алгорифма к слову в алфавите А, так как левые части этих формул не входят в такое слово.
Поэтому будут иметь место сле- дующие леммы: 4.1. Если й; Р ! — !Е, то б: Р 1- !',). 4.2. Если й: Р ! — ° !г, то б: Р ',— !е. 4.3. Если й: Р 1, где Р— слово в А, то б: Р ~1. На их основе с помощью леммы 4 25.4.7 легко доказы- ваются следующие леммы: 4.4. Если Р— слово в А и 6: Р (- ('!, то й: Р )- !е и !7 есть слово в А. 4.5. Если Р— слово в А и 6: Р 1 — ° !г, то й: Р ! — !г и !е есть слово в А.
4.5. Если Р— слово в А и 6: Р ~, то й: Р 1. Далее доказываются следующие леммы: 4.7. Если й:Р[= (г, то 6:Р)= !Е [4,1, 4,2), 4.8, Если й:Р[=(г 1, то 6;Р'Р=Я~ [4.1, 4.3]. 4.9. Если й(Р)~1), то 6(Р)~Д [4.7, 4.8]. РАСПРОСТРАНЕНИЯ АЛГОРИФМА !95 4.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
