markov_teorija_algorifmov (522344), страница 48
Текст из файла (страница 48)
Поэтому имеет место одно из трех: 1'. Х есть собственное начало В. 2'. 14 есть собственное начало Х. 3'. В3:Х. Пусть имеет место 1'. Тогда Х есть слово в АаЬ и су- ществует непустое слово Ф' такое, что (з) В ~г Х%'. Но тогда (4) ХЕУ ~ Х)УМ5 [(2), (3)] и, значит, '(5) ЕУ '~ )(РМ5 [(4)]. В силу (5) Е и Ю суть начала одного и того же слова.
Поэтому либо Е есть начало ИР, либо )(Р есть собственное начало Е. Предположим, что )У вЂ” собственное начало Е. Тогда существует непустое слово У такое, что Е м )УУ. Но тогда ' %'УУ х )УМ5 [(5)] и, значит, УУ ж М5. Обозначив первую букву слова У через т), мы видим отсюда, что она является первой буквой А-литероида М и, следовательно, отлична от Ь. Из (3) мы усматриваем, что последняя буква слова 11г также отлиина от Ь. Обозначим ее посредством $, Тогда для некоторых У' и Ф" будет ЕХВ"АУ', что, очевидно, невозможно [1,5]. так что, положив К =.= Х Ж 1.
Ж 2, видим, что в случае !' вхождение (1) имеет вид КМО 1(9)] где К вЂ” вхождение 1. в ]т' [(!О)]. Рассмотрим теперь случай 2 . В этом случае существует непустое слово ЯР такое, что (11) Х т я]р'. Но тогда (12) Я]]РИ'~ ]7МЗ [(2), (11)], и потому (13) ЮТ.У МЗ [(!2)]. В силу (13) ]У и М суть начала одного и того же слова По~~~му либо М есть начало слова Ж', либо В' есть собственное начало М. В первом случае (14) Яг л. МЕ для некоторого Л, и потому (15) МХА,УЛгМЗ [(13), (14)], откуда (16) гы ~З [(!5)]. Таким образом, (17) ХЖТ.ЖУя.йгМЛЖ(.Ж1' [(11), (14)] 256 сочетйния нОРмАльных АлгориФмов !Гл. Рр Значит, Т.
есть начало Яг, и потому существует слово 2 такое, что (6) Ф' х Т.Л. Но тогда (7) Т.У~ЫМЗ [(5), (6)] и, значит, У~ гмбх [(7)]. Таким образом„ (9) ХЖ(.ЖУ~ХЖТ.Жги [(!), (8)]. Но (!0) ХЫ:. д [(3), (6)] м! ПЕРЕВОД АЛГОРИФМА 257 положив К 2Ж7.Ж У, ' (18) идим, что при данном предположении Х Ж Т. Ж У л. ЯМК [(17), (18)], и тогда было бы МАРР(Л/ [(19), (22)], что ввиду непу- стоты ИР противоречит 1.2. Таким образом, остается пред- положить, что Т является собственным началом 7., т, е. что существует непустое слово У такое, что (23) Т.
Зг. ТУ. Но тогда (24) ТУУ Х ТБ [(21), (23)] и, следовательно, (25) )гУ Х 5 [(24)] [ Слова Т и У непусты, и, значит, 7., будучи А-литероидом, имеет вид аВа. Равенство (23) показывает, что последней бук- вой слова 1'является а, т. е. УлУ'а для некоторого У'. Анало- гично из (19) заключаем, что ТлТ'а для некоторого Т'. Но тогда 7. лТаУа ((23)] и, значит, Т' лкА, а У' есть иепустое слово в алфавите 5. Следовательно, 3 начинается буквой Ы(25)], что противоречит условию~леммы. Это завершает рассмотрение случая 2'.
В случае 3', когда Хейг, имеем (26) ХЩЩХМЗ [(2)], Э А. А. Марков, Н.'М. Нвгорквй ." .где К вЂ” вхождение 7. в 5 1(16)]. Покажем, что ]]У не может быть собственным началом М, В самом деле, допустим, что существует непустое слово 7 такое, что (19) М х ]]УТ. Тогда (20) Рут к РУТЗ [(13), (!9)], и потому (21) И' л. ТБ [(20)]. 7. не может быть началом Т, так кзк в этом случае существовало бы слово сг' такое, что (22) ТАЬШ, СОЧЕТАНИЯ НОРМАЛЬНЫХ АЛГОРИФМОВ 289 ПЕРЕВОД АЛГОРИФМА !гл.
ш и потому (27) Ь~'~ М5 1(26)). Следовательно, Ь начинается М или М начинается Ь. Отсюда по 1.3 ЬмМ, а значит, (28) )' х 5 ~(27Д, и потому ХФЬ х)'хг)7жМж5 г(1) (28)1 Таким образом, все случаи 1' — 3' рассмотрены. Утверждение 1.6 доказано. Отсюда легко следует 1.'7. В . Всякое вхождение А-литероида Ь в слово ЯМ, где М вЂ” А-литероид, а Я вЂ” слово в АаЬ, не оканчивающееся буквой Ь, имеет один из видов: КМ, где К вЂ” вхождение Ь в Я; Я ч' Ь ««, причем М х Ь. 1.8. Всякое вхождение А-литероида Ь в слово М5, где М вЂ” А-литероид, а 5 — слово в АаЬ, не начинающееся буквой Ь, имеет один из видов: МК, где К вЂ” вхождение Ь в 5; ««ЬФ5, причем МХЬ. 2.
Мы определим некоторую „грамматическую категорию" лят слов в алфавите АаЬ, называемых «А-вербоидами». О ьси эти слова будут двумя следующими правилами построе», предеВд 1. Пустое слово считается А-вербоидом. Вд 2. Всякий раз, когда построен А-вербоид Х, всякое слово, построенное как ХЬ, где Ь вЂ” любой А-литероид, считается А-вербоидом. Слово Х будет лишь тогда считаться А-вербоидом, когда об истинности высказывания «Х считается вербоидом» то ь можно будет заключить на основании правил В 1 В 2, р ~е мы будем называть правилами построения А-вербоидов.
Согласно определению А-вербоидами являются, пап име, следующие слова: Л, аЬЬа, аЬЬЬЬа, аЬЬЬааЬЬЬа. Процесс построения А-вербондов естественно распадается на шаги; иа каждом из них строится некоторый А-вербонд, причем применяется одно пз правил Вд 1 или Вд 2. Ввиду такого «индуктивного» характера определения поятия А-вербоида — Определения путем описания процесса х построения — для доказательства общих высказываний об А-вербоидах применйм метод индукции по построению, состоя,щий в следующем. Пусть мы хотим доказать, что всякий А-вербоид удовлетворяет некоторому одноместному вербальному предикату Р.
'Для этого мы доказываем: во-первых, что Л удовлетворяет Р'; во-вторых, что всякий раз, когда какой-нибудь А-вербоид Х удовлетворяет Р, всякий А-вербоид ХЬ, где Ь вЂ” какой-нибудь А-литероид, тоже удовлетворяет Р. Тогда мы вправе заключить, что всякий А-вербоид удовлетворяет Р. В самом деле, прослеживая процесс построения какого-нибудь А-вербоида, мы видим, что на каждом шаге этого процесса строится некоторый А-всрбоид, удовлетворяющий Р. В частности, это относится к последнему шагу процесса, когда получается интересующий нас А-вербонд.
Методом индукции по построению легко доказывается следующее высказывание: 2.1. Всякий А-вербоид либо пуст, либо начинается и оканчивается А-лшпероидом. Иначе говоря, имеем 2.2. Всякий непустой А-вербоид начиноегпся и оканчивается А-литероидом. Методом индукции по построению также легко доказывается 2.3. Всякое слово вида ХУ', где Х и г' — А-вербоиды, есть А-вербоид. Докажем 2.4.
Оба крыла всякого вхождения А-литероида в А-вербоид суть А-вербоиды. Условимся на время доказательства говорить об А-вербоиде Х, что он правилен, если оба крыла всякого вхождения А-литероида в Х суть А-вербоиды. Требуется доказать, что всякий А-вербоид правилен. А-вербоид Л правилен, так как не существует вхождений А-литероидов в Л. Пусть Х вЂ” правильный А-вербоид, М вЂ” любой А-литеронд. Покажем, что А-вербоид ХМ правилен. Пусть Н вЂ” какое-нибудь вхождение А-литероида Ь в ХМ.
Согласно 1.7 имеет место одно из двух: 9» 260 сочвтлння ноемлльных Алгоеиэмов !гл. !о 1а 1 имеется вхождение К литероцда Е в Х такое, что (1) Н~КМ. 2'. Нп ХЖЬЖ и Е3:М. В случае 1' пусть Р— левое крыло К, Я вЂ” правое крыло К. Имеем Н~РЖЕЖОМ г(1)! и потому крыльями Н являются Р и ЯМ. Здесь Р и О де ь и О суть А-вербоиды в силу правильности Х. ЯМ также есть А-вербоид согласно Вд 1.
Таким образом, оба крыла Н суть А-ве- боиды. В случае 2' крыльями Н являются Х и Л. Оба эти слова суть А-вербоиды. Таким образом, А-вербоид ХМ правилен, что н требовалось доказать. Докажем 2.5. Оба крыла вхождения непустого А-вербоида в А-вербоид суть А-вербоиды. Пусть Н вЂ” вхождение непустого А-вербоида У в А-вер- боид Х. Согласно 2.2 У оканчивается А-литероидом, т.
е. су- ществуют слово 2 и А-литероид Е такие, что (2) У ьс 2Ь. Обозначая через Р и 9 соответственно левое и правое крылья Н, имеем (3) Х 3': РУО 3г Р2Е() 1(2Н, откуда следует, что Р2ЖЕЖО есть вхождение А-литероида Ь в А-вербоид Х. Я есть правое крыло этого вхождения, и потому, согласно 2.4, !г есть А-вербоид. Мы доказали таким образом, что правое крыло Н есть А- вербоид.
Лналогично усматривается, что левое крыло Н есть А-вербоид. Итак, теорема 2.5 доказана. 2.5. Если Х есть А-вербоид, а слово У таково, что ХУ есть А-вербоид, то У есть А-вербоид. В самом деле, ЖХЖ 1' есть вхождение Х в ХУ и У— правое крыло этого вхождения, Если Х,ь'Л, то У есть А-вербоид согласно 2.5. Если же ХИЛ, то 1' ь ХУ, и, следовательно, 1' есть А-вербоид, так как Х)' А-вербоид. ак есть вьп ПЕРЕВОД АЛГОРИФМА 26! Аналогично доказывается 2.7. Если У есть А-вербоид, а слово Х таково, что ХУ есть А-вербоид, то Х есть А-вербоид. Методом индукции по построению слова доказывается с по- мощью 1.1 высказывание 2.8. Всякий А-вербоид есть слово в алфавите Аад.
3. Пусть Б — какой-нибудь алфавит, не имеющий общих букв с алфавитом А. Занумеруем его буквы слева направо, начиная с первой, которой припишем номер 1. Ввиду того, что для всякой буквы алфавита Б имеется единственное ее вхож- дение в этот алфавит, каждая буква алфавита Б получит един- ственный номер. Номер буквы $ обозначим ч($). ч($) может быть охарактеризовано как натуральное число, на единицу большее длины левого крыла вхождения а в Б. Каждой бук- ве $ алфавита Б поставим в соответствие слово (1) !Б (5) = аьь пза в двухбуквенном алфавите аб.
Это слово будем называть Б-пе- реводом буквы 5. Кроме того, Б-переводом всякой буквы т! алфавита Л будем считать эту самую букву нр гБ (т)) т! где 1Б (т)) означает Б-перевод буквы 5 алфавита Л. Мы таким образом определили Б-перевод всякой буквы алфавита АБ. Очевидно имеем следующие верные выска- зывания: 3.1. Б-перевод всякой буквы алфавита АБ есть Л-ли- тероид. 3.2.
Б-переводы двух различных букв алфавита АБ раз- личны. Таким образом, имеем верное высказывание З.З. Если ь и Х вЂ” буквы алфавита АБ, то ьХу, тогда и только тогда, когда 1г, (5) ь !Б (7). Обозначение !Б можно рассматривать как знак некото- рой операции над буквами алфавита ЛБ. 4. Операцию (Б, определенную до сих пор для букв алфавита АБ, мы теперь распространим на слова этого алфавита, положив (1) !ТА Б (Л) — Л, (2) лА, Б (Рь)" ч А, а (Р) (Б ($) для любого слова Р в алфавите ЛБ и для любой буквы $ этого алфавита. 262 сОчатАния нормАльных АлГОРиФмов !Гл.
1Р Очевидно, что (3) йА, Б (ь) ~ (Б (ь) для любой буквы $ алфавита АБ; (4) лА, Б (~%)~с ФА, Б (Р)ЛА, Б((Е) для любых слов Р и Я в алфавите АБ. Результат применения операции АА Б к слову Р в алфавите АБ мы будем называть (А, Б)-переводол«слова Р. В силу (3) это определение согласуется с определением Б-перевода буквы алфавита Б (см. и. 3). Согласно 2 33 имеется нормальный алгорифм, перерабатывающий всякое слово в алфавите АБ в (А, Б)-перевод этого слова.
Там, где это не будет вызывать недоразумений, мы будем писать просто «перевод> вместо «(А, Б)-перевод». Мы будем также опускать индексы А и Б у букв»х и Г. 4.1. Перевод всякого слова в алфавите АБ есть А-вербоид. Это доказывается индукцией по построению слова в алфавите АБ с помощью (1), (2) и 3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
