markov_teorija_algorifmov (522344), страница 42
Текст из файла (страница 42)
В самом деле, 17.,(й,(8,(21,(9,(й,(Р)))))) =14 ([й(Р)-Е(Р)) [2.5] й (р) З(р) [2 7] Условное равенство (1) следует теперь из (5) и 2.8. 3. Теорема 1.1 может быть доказана следующим образом. Пусть, в самом деле, й и ч) — какие-либо нормальные алгорифмы, и пусть А — объединение их алфавитов. По- строим формальные распространения й, н 6, алгорифмов й и А) на алфавит А. Алгорифмы й, и лз, суть нормальные алгорифмы в одном и том же алфавите А, и потому к ним может быть применена теорема 2.1, Согласно этой теореме жет быть построен такой нормальный алгорифм (т над , что для любого Р в А имеет место условное равенство (г (Р) й, (Р) 2), (Р). ринимая во внимание, что Я(,(Р) й (Р) 2), (Р) 1л)(Р) 35.5.4], получаем отсюда условное равенство 1(2).
4. С помощью теоремы 1.1 может быть доказано слеующее утверждение: 4.1. Пусть й и 'У вЂ” произвольные нормальные алгорифмы, А — объединение их алфавитов, а 7 — какая-либо буква. :левада может быть построен нормальный алгорифм СВ над итом А 0 (7[ такой, что для любого слова Р в А бут выполняться условное равенство й(Р) =й(Р)7В(Р). В самом деле, пусть Э означает нормальный алгорифм Ац [7), перерабатывающий всякое слово в этом алфавите слово 7. Как строится такой алгорифм, нам известно Ч 29.3]. Применив теорему 1.1 сначала к алгорифмам й З, а затем к получаемому в результате этого алгорифму алгорифму 6, мы получим нормальный алгорифм б над лфавитом А () (7) такой, что для любого слова Р в А будет выполняться условное равенство (1(Р) й(Р)З(Р)2)(Р)„ (1(р) =й(Р)7Б(р), то и требовалось доказать. 5.
Формулируем некоторые следствия из доказанных еорем. 5.1. Каков бы ни был нормальный алгорифм й над атом А, могут быть построены такие нормальные горифмы (1 и т' над А, что для любого слова Р в А имеют сто условные равенства ) (5(Р) й (Р) Р, ) А.
(Р) Рй (Р), Для доказательства воспользуемся тождественным нор- льным алгорифмом в алфавите А [2 28.4]. Применяя тео- му 1.1 к алгорифму й и тождественному алгорифму в А з 391 224 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРНФМОВ сГСС. СЧ РАЗВЕТВЛЕННЕ АЛГОРИФМОВ 225 (в роли 2)), получаем нормальный алгорифм 6 над А, для которого справедливо условное равенство (!) Подобным же образом, с переменой ролей алгорифма Я и тождественного алгорифма, получаем нормальный алгорнфм ~ над А, для которого имеет место (2).
5.2. Каковы бьс ни были нормильньш алгорифм Я над алфавитом А и буква у, существуют такие нормальные алгорифмы 6 и Тс над алфавитом А() (у), что д)ля любого Р в А имеют лсесто условные равенства 6(Р) ~61 (Р)уР, Тс(Р) ' Руй (Р). Это доказывается аналогично 5.1 с применением 4.1 вместо 1.1. 6. Нормальный алгорифм 6, построенный способом, указанным в доказательстве теоремы 1.1, в существенном однозначно определяется нормальными алгорнфмамн Я и »с). Мы будем называть его нормальным объединением алгорифмов й и «3.
Нормальное объединение алгорифмов Я и 2) мы будем обозначать символом (й «В). Следующие утверждения резюмируют предыдущее: 6.1. Для любых двух нормальных алгорифмов й и сО существует «) нормальное объединение (Я л)). 6.2. Нормальное объединение нормальных алгорифмов Я и «1 есть норлсальный алгорифм над объединением алфавитов этих олгорифмов. 6.3, Для любых двух нормальных олгорифмов Я и ЯС имеет место условное равенство (Я «1«)(Р) ~ Я (Р) 21(Р) где Р— лобов слово в объединении алфавитов эпшх алгориЧ'- мов. $ 36. Разветвление алгорифмоа 1.
Иногда приходится строить предписания следующего типа: «применить к исходным данным алгорифм й или алгорифм «В в зависимости от того, обладают ли этн данные какимто свойством». Для того чтобы такое предписание можно было рассматривать как алгорнфм, необходимо, разумеется, чтобы «) См ВЗА6 ' 'существовал конструктивный метод распознавания свойства ':исходных данных, о котором идет речь.
Этот метод может, например, состоять в применении к исходным данным некото- ' рого специально подобранного распознающего алгорифма, перерабатывающего исходные данные в пустое слово тогда н только тогда, когда они обладают интересующим нас свойством. Чтобы узнать, обладают ли этим свойством исходные данные, нужно будет тогда применить к ним распознающий алгорифм и посмотреть на результат этого применения. Свойство имеет место, если этот результат есть пустое слово, и не имеет места, если он есть непустое слово. В первом случае предписание требует применить к исходным данным алгорифм Я, во втором — алгорифм л). Переходя от алгорифмов , вообще к вербальным алгорифмам, т. е.
к алгорифмам в некоторых алфавитах, мы приходим к предписаниям следующего , типа. Даны вербальные алгорифмы й, е) и 6 в алфавите А. ' Предписывается, исходя из произвольного слова Р в этом алфавите, применить к нему алгорифм 6. Если в результате получится пустое слово, то надлежит применить к Р , алгорифм Й; если же получится непустое слово, то надлежит применить к Р алгорифм »В. Это предписание можно рассматривать как некоторый вербальный алгорифм в А. Для его применимости к слову Р в А, разумеется, необходимо, чтобы алгорифм 6 был применим к Р.
Мы приходим, таким образом, к некоторому сочетанию трех вербальных алгорифмов Й, 6 и 6 в А, являющемуся новым вербальным алгорифмом в А. Это сочетание естественно называть разветвлением алгорифмов й и»В, управляемым алгорифмом 6. Естественно спросить, является ли разветвление двух нормализуемых алгорифмов, управляемое третьим нормализуемым алгорифмом, также нормализуемым алгорифмом. Положительный ответ на этот вопрос подсказывается прин. цинам нормализации.
Он вытекает из следующей теоремы: 1.1. Теорема разветвления, Каковы бы ни были нормальные алгорифмы Й, 6 и 6, мажет быть построен нормальный алгорифм лэ над объединением А их алфавитов лип«ой, что для любого слова Р в А выполняются следующие три условия: (1) если 6(Р) я.Л, то лэ(Р) ~ й(Р), (2) если 6(Р) л(.'Л, то лэ(Р) ж я) (Р), (3) если определено йс(Р), то определено и 6(Р).
8 А, А. Марков, Н. М. Нагоркыь 226 СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ [ГЛ. ГУ Здесь и в дальнейшем знак «~Г», когда Он связывает выражения, могущие оказаться не определенными, надле- жит понимать следующим образом. "оба выражения, связы- ваемые этим знаком, имеют смысл, н их значения явля- ются графически различными словами. Доказательство теоремы разветвления составляет глав- ное содержание этого параграфа. 2. Докажем некоторые леммы. 2.1. Каковы бы ни были нормальный алгорифм 6 в ал- фавите А и буква и, может быть построен такой нормаль- ный алгорифм 6 над А() (а), что (а для слов Р в А таких, что 6(Р)хЛ, (1) 6(Р)~~ [Л для слов Р в А таких, что 6(Р)В.Л, и что 6 применйм к тем и только к тем словам в А, к которым применйм 6.
Воспользуемся разветвляющим нормальным алгорифмом 2(А ИВ»ИА,ФА над алфавитом А В (а), пеРеРабатывающим Л в с», а всякое непустое слово в алфавите А () (а) — в Л [5 30.1]. Для сокращения письма обозначим его через 6,, Имеем (2) 6,(Л) Хс», (3) 6,(Р)ХЛ (Р— слово в А, Р)~Л).
Построим искомый алгорифм 6 как нормальную композицию алГОрнфмОВ 6 и 6«: (4) 6 м. (6, С). Алгорнфм 6, как н б„есть нормальный алгорнфм над А ()(а) и (5) 6 (Р) — 6» (6(Р)) (Р— слово в А) [(4), $ 37.4.3] Если Р— слово в А и 6(Р) ЛЛ, то 6 (Р) 6, (Л) [(6)] х а [(2)]. Если же Р— слово в А и 6(Р) д Л, то 6(Р) есть слово вАИ 6 (Р) лг Л [(6), (3)], Таким образом, алгорифм 6 удовлетворяет условию (1).
В силу (5) алгорнфм 6 применим лишь к тем словам в А, к которым применим 6. С другой стороны, согласно уже доказанному, он применим ко всем таким словам. Лемма, таким образом, доказана. РАЗВЕТВЛЕНИЕ АЛГОРИФМОВ 2.2. Каковы бы ни были нормальный алгорифм 6 в алвите А и буква с», может быть построен такой норьный алгорифм $ над А 0(а), что ] аР для таких слов Р в А, что 6(Р) ХЛ, ~(Р) ~- Р для таких слов Р в А, что 6(Р) 1Г Л, что $ будет применим к тем и только к тем словам в А, к которым применим 6. В самом деле, построим алгорифм 6 согласно предыду,щей лемме. Построим затем, согласно ~ 38.5.1, такой нормальный алгорифм»т над А В (а), что (7) ~(Р) ж 6(Р) Р (Р— слово в А()1а)). Он, очевидно, применим к тем и только к тем словам в А, к которым применим 6, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
