markov_teorija_algorifmov (522344), страница 39
Текст из файла (страница 39)
Следовательно, 1Х': О» — ° )7. Но тогда 131': Р~Д»- ° )с, и, значит, Й' применим к Р, что и требовалось доказать. Условимся теперь в следующей терминологии. Если Р, Т, 5 — слова в А и Тр А, то образом вхождения 77 7К Т Хг 5 в алфавите А будем называть вхождение а [)г 7К [Т Хг [5 в алфавите Аа. Кроме того, образом вхождения гьгК 5 в алфавите А будем называть вхождение Хг сг 7К [5 в алфавите Аа. Тем самым, образ определен для вхождений в алфавите А с непустой основой, а также для первых вхождений пустого слова в слова в этом алфавите. 2.23. Образ вхождения в слово Р есть вхождение в сло- во а[Р, 2.24. Образ вхождения непустого слова Т есть вхож- дение с.гово [Т Это непосредственно следует из определения образа.
2.25. Если Р— слово в илфавипи' А, то всякое вхождение двойника непустого слова Т в алфавите А в слово а[Р" есть оораз некоторого вхождения слава Т в слово Р. В самом деле, пусть Р— слово в А, (18) (7ж[Т-ела — вхождение двойника непустого слова Т в алфавите А в слово а[Р . Тогда (17) (7 [Т Ж' яс а [Р зг! КОМПОЗИЦИЯ ГОРИФМОВ 207 откуда следует, что непустое сло о (7[Т начинается буквой а, Так как [Т вЂ сло в алф вите А, не содержащее 'б кву и, этой буквой начинается Ой Таким образом, суще- У ствует такое слово Х, что (18) (7 я аХ. Имеем теперь (19) о!Х[7 (!У о с![Р [(17), (18)], (20) Х [Т-й7 Х [ — [(10)].
, Так как [Р— слово в А, Х и В' также суть слова в А ,' [(20)]. Поэтому существуют такие слова )7 и 5 в А, что (21) Х в[)7, : (22) В' х [5-, Следовательно, (7 7»г [Т Ж ((7 Х а [)1г 7К [Т гК [5 [(18), (21), (22)], ' а это означает, что рассматриваемое вхождение (16) есть образ вхождения )7 7КТ7К5 непустого слова Наконец, (23) [)7 [Т [5 я. [Р [(20), (21), (22)], (24) [)7Т5- х [Р- [(23), (5)], )ггт5 Х [(24), 2.8], т. е, 177КТгк5 есть вхождение в Р. Таким образом,' рассматриваемое вхождение есть образ некоторого вхождения Т в Р, что и оставалось доказать.
2.26. Оепустое слово Т в алфовигпе А тогда и только тогда входит в слово Р в этом алфавите, когда его двойник входит в слово а [Р . В самом деле, если Т входит в Р, то существует вхож- Т Р. Так как Т л'А, образом этого вхождения дание '! является некоторое вхождение [Т в а 7 [, ', Следовательно, двойник Т входит в [ Обратно, если [Т входит в и»Р, то существует вхож- ение,"Т в игР . Согласно 2.25 это вхождение есть образ дение ' в и[ . о некоторого вхождения Т в Р.
Гледоват ль ельно, Т входит в Р, что и требовалось доказать, 2.27. Если Р— слово в алфавите А и вхождение К не- пустого слова Т в Р предшествует вхождению Е слова 'Т в Р, то образ К предшествует образу 1„ В, и еле, п сть )(' и (7 означают соответственно В самом деле, пусть . Если К п едшествует 1., левые крылья вхождений К и 7.. Если К пр д ссчетАния нОРмдльных ААГОРиФИОЗ !ГЛ. >Р то Р есть собственное начало 1>. Поэтому существует такое непустое слово Х, что (25) П 2': ЯХ. Имеем а [П- о а [Я- [.Х- [(28),(5)], ьде [Х:ле Л.
Следовательно, а [Я есть собственное начало а[6 . Но, по определению образа, а[И и сл[ь> суть соответственно левые крылья образов вхождений К и Е. Следовательно, образ К предшествует образу Е, что и требовалось доказать. 2.28, Если непустое слово Т входит в слово Р в алфа- вите А, то образом первого вхождения Т в Р является первое вхождение [Т в а[Р В самом деле, пусть К вЂ” первое вхождение Т в Р.
Тогда образ К есть вхождение [Т в а[Р- [2.23,2.24]. Рассмот- рим теперь произвольное, отличное от образа К вхождение М слова [Т в слово а [Р . М есть образ некоторого вхождения Е слова Т в слово Р [2.25]. Е~.'К, так как образ Е отличен от образа К. Так как К вЂ” первое вхожде- ние Т в Р, К предшествует Е. Поэтому образ К предше- ствует образу Е [2.27], т. е. М. Следовательно, образ К предшествует всякому отличному от него вхождению [Т в а[Р, т. е. является первым вхождением [Т в а[Р-, что и требовалось доказать.
2.29. Пусть Р— формула подстановки алгорифма Е', 6 — соответствующая формула системы ВВ, Р— слово в А. Левая часть Р тогда и только тогда входит в Р, когда левая часть 6 входит в а [Р В самом деле, если левая часть Р есть непустое слово, то левая часть 6 есть двойник этого слова [2.10], и утверж- дение леммы вытекает из 2.26.
Если же левая часть Р есть пустое слово„то левая часть 6 есть слово а [2.10]. Утверж- дение леммы верно н в этом случае, так как Л входит в Р, аа — ва[Р 2.30. Если в условиях предыдущей леммы левая часа>ь Р входит в Р, то первое вхождение левой части 6 в а[Р есть образ первого вхождения левон части Р в Р. В самом деле, пусть соблюдены условия предыдущей леммы, и пусть левая часть Р входит в Р. Если левая часть Р— непустое слово, то левая часть 6 есть двойник этого слова, и утверждение леммы вытекает из 2.28.
Если >ке левая часть Р†пуст слово, то левая часть 6 есть лзп КОМПОЗИЦИЯ АЯГОРИФМОВ 209 слово а [2.!О], Первым вхождением левой части Р в Р вляется вхождение >к>К Р, а первый,(и единственным) вхож. дением левой части 6 в а[Р— вх61кдение >Колк [Р . Так как >ха>ь[Р- есть, согласно опредерению, образ >К>КР, лемма доказана. Докажем теперь некоторые леммы, связывающие работу ;~,' алгорифма 6 с работой алгорифма л>'. 2.31. Если В': Р [ — 6, >по 216 а[Р 1- а[ч> В самом деле, пусть я)': Р 1 — 6. Среди формул подстановок алгорифма Ь' имеются формулы с левой частью, входящей в Р. Пусть Р— первая из них. Она простая, так как 9>: Р 1 — (г.
Пусть 1l и У означают соответственно левую и правую часть формулы Р. Пусть А»ь 1>' >К.9 — первое вхождение Е> в Р. Так как алгорифм ч) в применении к Р предписывает подставить У вместо Р >К 6 >К 5 и В': Р )- 1~, имеем (26) 6 я.)сУ3. Пусть, далее, 6 — формула системы 9)а, соответствующая Е. Ее левая часть входит в а[Р, так как левая часть Е входит в Р [2,29].
С другой стороны, левые части формул системы к)Р„, стоящих выше 6, не входят в я[Р так как эти формулы соответствуют формулам схемы л)', стоящим выше Р, а левые части последних не входят в Р [2.29]. Таким образом, 6 есть первая формула системы Ба с левой частью, входящей в а[Р Левые части формул, представленных первыми семью строками схемы (3), также не входят в слово а(Р, так как каждая из этих левых частей содержит букву алфавита Ар, не входящую в а[Р, Следовательно, 6 есть первая формула подстановки алгорифма 6 с левой частью, входящей в и [Р . В применении к этому слову алгорифм 6 предписывает поэтому подставить правую часть формулы 6 вместо первого вхождения ее левой части. Это вхождение есть образ первого вхождения левой части Р в Р [2.30], т.
е. вхождения Р >ь Е»ь О. Таким образом, алгорифм 6 в применении к слову а[Р предписывает подставить правую часть 6 вместо образа вхождения Р>ь1>'>ьо'. В дальнейшем будем различать два случая: П ~гЛ и 1>'МЛ. а) Пф.Л. В этом случае образом Р >КО>РО является вхождение а[Я >ь[6 >К[О, а правой частью формулы 6 является двойник правой части формулы Е [2,11], т. е. слово [У, Принимая во внимание, что формула 6 простая [2.9], 21О сочетлния иоемлльиых ллгоеиФмов 1гл. ~у имеем б: а[Р 1- я[И [У й: а [)х'У5 [(5)) Х а [Я [(26)].
б) 0 а Л. В этом случае (2?) )7 х Л, так как Р 4с 0:К 5 — первое вхо кдение (/ в Р. Обра ом вхождения КФ (?Ф5 является поэтому вхождение Жая~[5, а правой частью формулы 6 является слово а[У [2,11], Принимая во внимание, что формула 6 простая [2.9), имеем б: а[Р- 1 — я[У [5 Х а [У5 [(5)] ~ а [)7У5 [(27)) х а [б [(26)]. Таким образом, в обоих случаях б: а(Р (-аЯ, что и требовалось доказать.
2.32. Если В': Р 1- ° Я, то существуют такие слова Я иТ, что () х)(7', (4: а[Р 1-а[Я (1[Т-, В самом деле, пусть Ю': Р )- ° Я. Как и в доказательстве предыдущеи леммы, рассмотрим первую среди формул подстановок алгорифма я)', имеющих левые части, входящие в Р. Пусть Р означает зту формулу. На этот раз Р— заключительная формула, так как хэ'; Р 1- ° (,1. Пусть (? н У означают соответственно ее левую и правую части, Пусть )х:К(?ж5 — первое вхождение (? в Р. Как и в доказательстве предыдущей леммы, б о ЙУ5. Пусть 6 — формула системы лэв, соответствующая Р.
Как и в доказательстве предыдущей леммы, убеждаемся, что в применении к слову а[Р алгорифм 1з предписывает подставить правую часть формулы 6 вместо образа вхождения )7ясУФ5. Опять различаем два случая: 0 5Л и 0 хЛ. а) (?.д. Л. В этом случае образом )7 Ф(?:К5 является вхождение а[я :К[(? Ф[5 , а правой частью формулы 6 †сло [)[У [2.12), Принимая во внимание, что фор- зп КОМПОЗИЦИЯ Л)и[ОРИФМОВ 21! ула 6 простая [2.9), имеем (лл а~[Р- ) — а[)( () [У [5 Х я [)7-[( [У5- .
[(5)]. б) 0 йЛ. В этом случае имеем равенство (27), так как )х:Кб:К5 — первое вхождение (? в Р. Образом вхождения ' )7 гк(?Ф5 является поэтому вхождение каж[5, а правой частью формулы б — слово а[)[У [2.12]. Принимая во внимание, что формула 6 простая [2 9), имеем хэ: а[Р 1- яр[1' [5 й а[) [У5 [(5)] лс а [)7 [) [У5 [(27), (4)). Таким образом, в обоих случаях (28) 6: а[Р 1 — а[И [)[У5 . ' Согласно (26) и (28) имеем 9 вКТ, (4: а[Р ) — а[)7 ЯТ ' где Т Ф У5, что и доказывает лемму. 2.33. Если )7 и 5 — слова в А, то 9: а[Я 13[5 )= [1[Ю . Доказательство — обычное для такого рода утверждений. , Сначала мы обнаруживаем, что ((: я[)х с1э[5 )-а[)7 Я[5 ; а затем проводим правую индукцию по )х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
