markov_teorija_algorifmov (522344), страница 20
Текст из файла (страница 20)
Если бы слово В было концом У, то имелось бы слово ][у такое, что (7) 6. Вхождение слова Р в слово ье, предшествующее всякому другому вхождению Р в Я, мы называем первым вхождением слова Р в слово се. Имеем очевидно 6.1. Если слово Р является началом слова 1е, то начальное вхождение Р в (е [4.П является первым вхождением Р в се.
6.2. Вхождение лслс Р есть первое вхождение пустого слова в Р [4.2, 6.1]. Докажем следующую теорему существования первого вхождения: 6.3. Если слово Р входит в слово Щ то сушрствует первое вхождение слова Р в слово сс. Пусть Р входит в «1. Тогда имеется вхождение Х слова Р в слово Я [3.4], Обозначим буквой ]у' глубину Х. Построим следующий одноместный арифметический *) предикат Р со свободной натуральной переменной М: «существует вхождение Р в се с глубиной М» или, что то же самое, «М есть глубина некоторого вхождения Р в (е». Предикат Р, как легко видно, разрешим.
Натуральное число Л[ ему удовлетворяет. Поэтому к Р и Ж применима теорема о наименьшем числе [э 21.2.1], согласно которой может быть построено наименьшее число, удовлетворяющее Р. Пусть это будет Е. Число Е удовлетворяет Р, тогда как всякое число, меньшее Ь, не удовлетворяет Р. Так как Е удовлетворяет Р, имеется вхождение У слова Р в се с глубиной Е. Покажем, что У есть искомое первое вхождение Р в се. Пусть 2 — какое-нибудь вхождение Р в сс, отличное от У. Согласно построению предиката Р глубина 2 удовлетворяет Р. Поэтому глубина 2 не меньше Е, т.
е. глубины У. Глубина 2 отлична от глубины У, так как 2~'.У [5.1П. Следовательно, глубина У меньше глубины 2 [3 18.6.8]. Поэтому У предшествует 2 [5.10]. Таким образом, У предшествует всякому другому вхождению слова Р в се, т. е. 1' есть первое вхождение Р в (], что и требовалось доказать. *) Арифмеми«ескина мы называем преднкаты с натуральнымн свобод- ними переменными. допустнмымн значенннмн таких переменных нвляютсн натуральные числа.
См. 1!03. семиотика [гл, н Истинность следующего высказывания почти очевидна: 6.4. Если слово Р входит в слово ф то первое вхождение сло- ва Р в че единственно (5.5). 7. Легко доказывается следующее высказывание: 7.1. Если Х вЂ” вхождение слова Р в слово Я, то КХ есть вхождение слова Р в слово )(Я и ХР есть вхождение слова Р в слово ф7, Согласно 7.1, если Х и У вЂ” вхождения слова Р в слово ~ч', то )хХ и РУ тоже суть вхождения слова Р в одно и то же слово 1хге'. Поэтому можно говорить о предшествовании вхождения 1хХ вхождению )хУ.
Можно также говорить о предшествовании вхождения ХР вхождению У)7. Легко доказываются следую- щие высказывания: 7.2. Если Х и 1' — вхождения слова Р в слово Я, то )хХ тогда и только тогда предшествует И', когда Х предшест- вует У. 7.3. Если Х и У вЂ” вхождения слова Р в слово 1~, то Х)х тогда и только тогда предшествует УР, когда Х предшест- вует 1'. Докажем высказывание 7.4. Если Х вЂ” первое вхождение слова Р в слово Я, то Х)т есть первое вхождение слова Р в (Я.
Пусть Х есть первое вхождение слова Р в слово 9. Обо- значая через 5 левое крыло Х, через Т правое крыло Х, имеем (1) Х о ВЖРЖТ, (2) ХР ~ЕЖ Р Ж Тй. ХР есть вхождение слова Р в слово ф7 [7.1]. Покажем, что Хй предшествует всякому другому вхождению Р в 9Р. Пусть У вЂ” вхождение Р в Яй, н пусть (3) У-)еХ)7.
Требуется доказать, что Х)т предшествует У. Обозначая через и левое крыло У, через У вЂ прав крыло У, имеем (4) ухижржу. Так как Х вЂ” вхождение в Я, а У вЂ” вхождение в 1е)т, имеем (5) я т — о [(1)], (б) иР =.()77 [(2)], (7) иРУ х ВГРТК [(5), (5)]. эзз ВХОЖДЕНИЯ юз Если бы мы имели и'нЕ, то имели бы также У Р, ыж7о [(7), ~ 17.5.2], и вхождения Х)т и У совпадали бы [(2), (4)] вопреки (3). Следовательно, (8) и7г- Е, Покажем, что и не .может быть собственным началом Е.
Допустим, что и — собственное начало Е. Тогда имеется слово )У такое, что (9) ех и)у, В силу (8) (10) )Уф: Л [(9)]. Имеем (11) РУдУРРТК [(7) (9)] В силу (10) и ф 19.2.3 ЕУР не есть начало Р. Поэтому Р есть начало %Р [(!1), ф 18,3,4] и существует слово К такое, что (12) тРР й.
РК. Имее Π— иРКт [(5), (9) (12)] Таким обРазом, (13) ижржКт есть вхождение слова Р в слово СГ. Левое крыло этого вхождения есть собственное начало левого крыла вхождения Х. Сл довательно, вхождение (13) предшествует вхождению Х. Зт иворечит тому, что Х вЂ” первое вхождение едоват о прот , что и— К этому противоречию мы пришли, предположив, что собственное начало Е. Следовательно, и не есть собственное о.
Поэтому 5 есть начало и (э 18.4.5, (7)). В силу (8) Я есть даже собственное начало и. Поэтому вхожд н предшествует вхождению У, что и требовалось доказать. Докажем высказывание 7.5. Если Х вЂ” первое вхождение слова Р в слово Я и Р не есть начало слова К~, то $Х есть первое вхождение слова Р в слоОбозиачая через и левое крыло Х, через 1' — правое р — к ыло Х, имеем ххижржу.
(14) Юл СЕМИОТИКА [Гл. н ЯХ есть вхождение слова Р в слово $О 17.1!. Требуется доказать, что ЕХ предшествует всякому отличному от $Х вхождению слова Р в слово $Ае. Пусть У вЂ” вхождение слова Р в слово $Х, и пусть (15) У -е3Х. Обозначая через В левое крыло )', через  — правое крыло г, имеем (16) 'г' 'ч.йЖРЖВ и (17) Врал $1г. Если бы слово Р было пустым, слово Р было бы началом слова $1'1 вопреки предположению.
Таким образом, Р КЛ и существуют слово Т и буква 11 такие, что (18) Е Хт1Т. Имеем (19) т1ТРБ Х Щ [(17), (18)], и потому (20) ц д $ [(19)], (21) ТРЯ:А Я [(19)], (22) В к ~Т [(1 8), (20)]. Таким образом, Т Ж Р Ж В есть вхождение слова Р в слово Я [(21)]. Имеем (23) ~Х Х ~О ЖРЖ У [(14)], (24) У ХК 7 Ж Р Ж В [(16), (22)].
Отсюда (25) $У ~~Т [(23), (24), (15), 5,1], (26) У )г Т [(25)], Т Ж Р Ж 3 ~. 'Х [(14), (26), 5,1]. Таким образом, ТЖ РЖЗ есть вхождение слова Р в слово 1;1, отличное от первого вхождения Х слова Р в слово 1е. Сле- довательно, Х предшествует ТЖРЖВ. Поэтому $Х пред- шествует $ТЖРЖЕ [7.2], т. е. $Х предшествует У [(24)], что и требовалось доказать. Из соответствующих определений легко следуют высказы- вания: ,: 4зз1 1ОЬ вхождения 7.6. Если слово Р входит в слово Я, то левое крыло первого вкождения слова Р в слово 1г есть начало левого крыла всякого вхождения Р в 1Е.
7.7. Если слово Р входит в слово 1Е, то правое крыло всякого вхождения слова Р в слово 1Е есть конец правого крыла первого вхождения Р в О. С помощью высказывания 3.11 легко доказывается 7.8. Слово В тогда и только тогда является левым крылом первого вхождения слова Р в слово Щ когда соблюдаются условия: а) КР есть начало 1г; б) каково бы ни было начало Е слова 9 такое, что БР также есть начало С(, тт' есть начало В. Аналогично с помощью 3.12 доказывается высказывание 7.9.
Слово Т тогда и только тогда является правам крылом первого вкождения слова Р в слово Я, когда соблюдаются условия: а) РТ есть конец 1е'; б) каков бы ни был конец У слова 1е такой, что Р(7 также есть конец Я, У есть конец Т. Легко доказывается высказывание 7.10. Если Р ~Г.Л и Р входит в 1г, то Р не входит в левое крыло своего первого вхождения в 1е. 8.
Слово РЕК мы будем называть резулыпатом подстановки слова В вместо вхождения Р Ж ~ Ж)т. Очевидно имеем 8.1. Для всякого вхождения Х и слова Я имеется однозначно определенный результат подстановки слова В вместо Х. Он является словом в рассматриваемом алфавите. Имеем далее 8.2. Если слово Ц вкодит в слово Т, то имеется однозначно определенный результат подстановки слова Е вместо первого вхождения слова 9 в слово Т. Он тогда является словом в рассматриваемом алфавите [6.3, 6.4, 8.11.
Результат подстановки слова В вместо первого вхождения слова О в слово Т мы будем обозначать символом г. (В, 1',1, Т). Таким образом, имеем 8.3. Выражение 2(Е, чг, Т) осмысленно тогда и только тогда, когда слова О входит в слово Т. В етом случае оно означает некоторое слово в рассматриваемом алфавите. Из определения результата подстановки слова вместо вхождения следует высказывание 8.4. Равенство 'йт" я. й (В, Я, Т) 106 СЕМИОТИКА 1гл. и имеет л«есто гпогда и только тогда, когда ил1ею«пся начало (7 слова 1« и конец 1' слова К такие, что: а) У есть левое крыло первого вхождения 6 в Т; б) г' есть правое крыло первого вхождения 1г в Т; в) 1»7 хУЯл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
