markov_teorija_algorifmov (522344), страница 43
Текст из файла (страница 43)
е. к тем и только к тем .словам в А, к которым применим 6. Соблюдение условия (6) для $ непосредственно следует из соблюдения условия (1) "для 6 в силу условного равенства (7). 3. Докажем теперь теорему 1.1. Пусть 2(, В и 6 — нормальные алгорифмы; А — объединение их алфавитов. Пусть 21„В, и 6, означают соответст.
венно формальные распространения алгорифмов Й, В и 6 на алфавит А. Фиксируем буквы а и ~), не принадлежащие А. Построим нормальный алгорифм $ над Аа согласно ' лемме 2,2 таким образом, чтобы этот алгорифм был применим к тем и только к тем словам в А, к которым применим б„и чтобы соблюдалось условие ']аР для таких слов Р в А, что 6,(Р) ХЛ, Р для таких слов Р в А, что 6,(Р) в Л. Построим нормальный алгорифм 2(» в алфавите Ар, определив его схемой (2) ]Р Построим нормальный алгорифм В,— замыкание алго' рифма В, [э 36.2], затем нормальный алгорифм В;» в ал, фавите А11 со схемой, получающейся из схемы алгорифма В, ' в результате замены каждой правой части 1г заключительных формул подстановок словом рчг, и, наконец, нормальный алгорифм В, в алфавите Аар со схемой ' (3) В» Мз СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОЕ !ГЛ.
17 6,(Р) я: Л [4 35.5.4, (5)1 5 (Р) Х аР [(1), (6)1, ~ (Р) — (ЙзьВ~) (б! (Р)) Ц 37.4 3 (4)~ — (Й,ь В,) (аР) [(7)1 — Й, (В, (аР)) — Й, (Р) Й, (Р) — Й (Р) [э 37.4.31 [3.51 [3.81 [Ц 35.5.41, т. е. 0(Р) ~Й(Р), так что условие 1(1) соблюдается. Искомый алгорифм З мы определим как нормальиую композицию (4) ((Й:В.).3) Непосредственное рассмотрение схем (2) и (3) позволяет формулировать приводимые ниже леммы 3.1 — 3.7. Небольшие детали в доказательствах этих лемм мы оставляем читателю, полагая, что к настоящему времени у него накопился достаточный для этого опыт. 3.1.
Если )с и Я вЂ” слова в А, то Й,()хрЯ) М.ХЯ. Действительно, в этом случае Й,: гсрЯ )- )7Я, откуда и вытекает справедливость нашего утверждения. 3.2, Если Й,: Р ! — !е, то Й,: Р г — (). 3.3. Если Й,: Р)- Я, то Й;. Р)-4. 3.4. Если Й,: Р ~, то Й,: Р ~. 3 3. Если Р в А, то В,(аР)тьР. 3.6. Если В,: Р 1- !с, то В,: Р 1- Я. 3.7. Если В,: Р 1- !е, то существуют слова )с и Я в А такие, что ггЯХЯ и В,: Р ! — )ТрЯ.
Из 3.2 — 3.4 вытекает 3.8. Для любого Р в А Й,(Р) Й,(Р). Из 3.6 и 3.7 вытекают следующие два утверждения: 3.9. Для любого Р в А !В,(Р) тогда и только тлогда, когда !В,(Р). 3.10. Если !В,(Р), то существуют слова )7 и Я такие, что РЯХВ,(Р) и В,(Р) ХОДЯ. Покажем теперь, что выполняются условия 1(1) — 1(З). Действительно, пусть (5) Й(Р) нЛ. Тогда (6) (7) РАЗВЕТВЛЕНИЕ АЛГОРИФМОВ 229 теперь условие 1(2). Предположим, что Р в А Проверим ,и что (8) Тогда (9) !ь, (рй) у (П) А: Йу»-,,сл. р 35.5.4, (ЗД [(1) (9)1 [3 37.4.3, (4)1 [(10)1 [9 37.4.31.
21. (В*(Р)) н Й. ФР) [(18)1 х)7Я [3. 11 З: В, (Р) [(17)1 ХВ(Р) Ц 35.5.4~, т. е. Й,(В,(Р))йВ(Р). и аной части Осталось показать, что из осмысленности право части равенства ч (12) следует осмысленность его левой части. Итак, пусть (19) 1В (Р). Тогда (20) !В, (Р) [% 35.5.41, (21) В,(Р) Аьй!)Я (Р) З~ Л (Р) о Р (Р) =(Й;В,) (6(Р)) (Й,ОВ,) (Р) ж Й,(В,(Р)) ' Покажем, что " (12) Й (В (о)) ~ В (Р), Действительно, пусть осмыслена левая часть этого равен- ' ства, т.
е. пусть (13) !Й,(В,(Р)). " Тогда ' (14) !В, (Р) [(13)1, (15) !В,(Р) [3.9, (14)1, (16) !В(Р) Р 35.5.4, (15Д, ' т. е. осмыслена правая часть равенства (12). Кроме того, существуют слова )7 и Я в А такие, что (17) РЯ х В, (Р) и (18) В, (Р) я Ц1Я [3. 101, СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 1гл. г« для некоторых слов )г и В в алфавите А, А тогда (22) Й,(Р~З) мЯВ ~З.Ц, т. е. Й»(В»(Р)) осмыслено 1(21), (22)~. Таким образом, условное равенство (12) соблюдается, так что имеем В(Р) ~В(Р) 1(11)1, Итак, условие 1(2) проверено. Осталось проверить условие 1(3).
Оно также соблюдается. Действительно, пусть для некоторого Р в А !й(Р). Тогда 1$(Р) [(4)1, и, значит, (6,(Р) (2.2(, а потому и !6(Р) 13 33,3,41. Таким образом, теорема 1.1 доказана, 4. Нормальный алгорифм А~, построенный только что описанным способом н в существенном однозначно определяемый нормальными алгорифмами Я, 2) и 6, мы будем называть нормальным разветвлением алгорифмов Й и 6, управляемым алгорифмом 6. Мы будем обозначать этот алгорифм символом (Й У З ~ 6) й 40. Повторение алгорнфма 1. Е математике часто бывает нужно строить предписания следующего типа: «применить к исходным данным заданный алгорифм Й; если результат применения не обладает таким-то свойством Чз, применить к этому результату алгорифм Й; если и этот результат не обладает свойством ч), применить и к нему алгорифм Й и т.
д., до тех пор, пока не получится объект, обладающий свойством 4)». Для того чтобы такое предписание можно было рассматривать как алгорифм, необходимо, конечно, наличие конструктивного метода распознавания свойства Ч», Этот метод может, напри. мер, состоять в применении к рассматриваемому объекту „распознающего" алгорифма, тогда и только тогда перерабатывающего этот объект в пустое слово, когда он обладает свойством ((). Переходя теперь от алгорифмов вообще к вербальным алгорифмам, т. е.
к алгорифмам в некоторых алфавитах, мы приходим к предписаниям следующего типа. Даны вербальные алгорифмы Й и 6 в алфавите А. Предписывается, исходя из произвольного слова Р в А, применить к нему алгорифм Й, что (в случае применимости) даст слово Р,; к Р, надлежит применить алгорифм 6 и, если в результате получится непустое слово, предписывается <о 1 поетогение Алгоеифмл 2З1 рименить к Р, алгорифм Я, что (в случае применимости) аст слово Р;, с ним надлежит поступать так же, как с Р„ н т.
д.; этот процесс следует оборвать, когда получится 'слово Р„, перерабатываемое алгорифмом 6 в пустое слово. Мы пришли, таким образом, к некоторому сочетанию алгорифмов Й и 6 в А, сочетанию, являющемуся вербальным алгорифмом в А. Это сочетание мы будем называть повторением олгорифма Й, управляемым алгорифмом 6. Естественно спросить, является ли нормализуемым по.вторение ие нормализуемого алгорифма, управляемое нормализуемым алгорифмом.
Положительный ответ на о р подсказывается принципом нормализации, Он и в самом е б ет вытекать из теоремы 3.1, к формулировке кото- деле удет выт ой мы сейчас перейдем. Однако перед этим м нам пот е- Р- рой буется провести небольшую подготовительную р у, абот свя. занную с тем, что в приведенной выше пока еще не уточ- НЕННО" енной постановке задачи мы воспользовались переменным индексом и словооборотом <и т. д.», чего ранее не случалос . ' Мы хотели бы показать читателю, что это было всего лишь анью привычке и что точное изложение легко и удобно данью привы , укладывается в рамки принятого нами нндукти ивного стиля.
2. Пусть Й вЂ нормальн алгорифм в алфавите А, не содержащем знака у в качестве буквы. Итерационной цепью алгорифма Й мы будем называть всякую у-систему В в алфавите А, удовлетворяющую елею ему условию: всякий раз, когда слово Р соседствует 'душ у : в 5 слева со словом 9, т. е. когда слово ТРЯу д вхо ит в О', имеет место равенство Й(Р) я.1е. Легко видеть, что 2.1. Всякая у-система в алфавите А, входящая в итера- ~ ционную цепь алгорифма Й, сама является итерационной '4., цепью алгорифма Я. $ 2.2. Если 8 — итерационная цепь алгорифма Й с посленим членом Р и Й (Р) я.<г, то О()Т является итерационной цепью алгорифл<а Й с последним членом <Е.
Итерационную цепь О' — как, впрочем, и любую т-систему — мы будем называть многочленной, есл 3. Целью настоящего параграфа является доказательство следующей теоремы: 3.1. Теорема повторе пня. Каковы бы ни были нормальные алгорифмы Я и 6, может бьипь построен нормальный алгорифм 13 над объединением А их алфавитов со следующим свойством: 2) тогда и только тогда перерабатывает слово Р в алфавите А в слово <г, когда 'Я) существует многочленная итерационн я цепь 5 алгорифма Й, 232 сочвтлния нормлльных ллгориФмов 1гл.
гч соединяющая Р с (Е и такая, что 6 перерабатывает в не- пустое слово всякий внутренний*) член о', Начнем с доказательства следующей леммы. 3,2. Если ег — нормальный алгорифм в алфавите А и [) — буква этого алфавита, то может быть построен нормальный алгорифм 9 над А со следующим свойством: Э тогда и только тогда перерабатывает слово Р в алфавите А в слово (е, когда ге есть слово в А, начинающееся буквой 6, и существует многочленная итерационная цепь 5 алгорифма ггл, соединяющая Р с Я и такая, что всякий ее внутренний член не начинается буквой гг.
Пусть, в самом деле, л — нормальный алгорифм в алфавите А, р — буква А. Введем букву а, не принадлежащую А, и построим нормальный алгорифм 6 в Аа с сокращенно записанной схемой $а ас ар- »г (г( гг где $ пробегает А, а й" имеет тот же смысл, что и в доказательстве теоремы 4 37.2.1. Э есть нормальный алгорифм над А.
Покажем, что он обладает требуемым свойством. Для этого заметим прежде всего, что все, сказанное в доказательстве теоремы 9 37.2.1 о системе формул вХ", сохраняет силу и сейчас. В частности, справедливы леммы 2 37.2.2 — $ 37.2.6. Принимая это во внимание, легко убедиться в справедливости формулируемых ниже лемм 3.3 — 3.6. Доказательства этих лемм мы опускаем, так как они повторяют — с небольшими изменениями в сторону упрощения —- доказательства лемм 9 37.2.7 и 9 37.2.14 — 9 37.2.16 соответственно. Итак, имеем З.З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
