markov_teorija_algorifmov (522344), страница 16
Текст из файла (страница 16)
Условимся на протяжении данного доказательства го- ворить, что Я стройно, если, каковы бы ни были его начала Х и У, одно из них является началом другого. Требуется до- казать, что всякое слово стройно. Пустое слово Л стройно 12.3, 2.11. Пусть 2 — стройное слово, $ — буква. Докажем, что слово 2$ стройно. Пусть Х и У вЂ” начала Я$. Тогда имеют место дизъюнкции: (6) «Х — начало Я или Х м.св», (7) «У — начало 2 или У 1кЯ$». Если имеют место первые их дизъюнкций (6) и (7), то Х вЂ” начало У или У— так как слово 2 стройно.
Если имеет место второй юнкции (6), то У вЂ” начало Х, так как У вЂ” начало с$. Наконец, если имеет место второй член дизъюнкции (7), то Х вЂ” начало У, так как Х— начало с$. Таким образом, во всех слуФ~ях Х вЂ” начало У нли У вЂ” начало Х, что и требовалось доказать. Мы называем теорему 3.4 теоремой о двух началах. Аналогично имеем теорему о двух концах 3.5. Если Х и 1 — концы 2, то Х вЂ” конец У или У— конец Х. 4.
Будем говорить, что Х есть собственное начало У, если Х вЂ” начало !' и Х)~У; будем говорить, что Х есть собственный конец У, если Х вЂ” конец У и Хя У. 4.!. Х тогда и только тогда является началом У, когда Х вЂ” собственное начало У или Хх) [з 11.7,21. 4.2. Х тогда и только тогда является концом У, когда Х вЂ” собственный конец У или ХНУ [Я 11,7.21.
Докажем следующую лемму, понимая отрицание в ней как усиленное: 4.3. Рс не есть начало Р, В самом деле, утверждение леммы означает, что не существует слова Х такого, что (') Р ь РВХ. Преднкат графического равенства разрешим, и его прямым отрицанием является преднкат графического различия Ц 11.71. Поэтому усиленным отрицанием нашего утверждения является высказывание: каково бы ни было Х, (2) Р д'РяХ. Докажем его.
Действительно, пусть Р, 8, Х произвольны, и пусть (1) истинно. Тогда Лв 5Х [~ 17.5.11, что неверно в силу определения графического равенства [Ц 2,41. Следовательно, (1) ложно, и потому, в силу определения графического различия [3 2.41, (2) истинно, что и требовалось доказать. Теперь докажем теорему 4.4. Х гногда и только тогда является собственным началом Р«, когда Х вЂ” начало Р. « 181 НАЧАЛ 78 свмиоункА [гл, и Пусть Х вЂ” собственное )«йчало слова РК, Тогда Х вЂ” на- чало Рч и Х-у"Рг Поэтому Х вЂ” начало Р или Хя Р$.
Вто- рой член последней диз;ибикции отпадает, и потому Х вЂ” на- чало Р, Допустим теперь1'с другой стороны, что Х вЂ нача Р. Тогда Х~Рв [4,3).' Вместе с тем Х вЂ” начало РК [2.41. Таким образом, Х вЂ” собственное начало Р$. Имеют место следующие модификации теоремы о двух на- ' чалах: 4.5. Если Х и 1' — начали Е, то Х вЂ” начало У или У— собственное начало Х 13.4, 4.1, 2.!1. 4.6. Если Х и У$ — начала 2, то Х вЂ” начало У или У$— начало Х !4.5, 4.41. Аналогично теоремам 4.3 — 4.6 могут быть доказаны сле- дующие четыре теоремы: 4.7.
Слово ~Р не является концом слова Р. 4.8. Слово Х тогда и только тогда является собственным концом 7Р, когда Х вЂ” конец Р, 4.9. Если Х и У вЂ” концы 2, то Х вЂ” конец У или У— собственный конец Х. 4.10. Если Х и $У вЂ” концы Е, то Х вЂ” конец У или $У— конец Х. 4.11. Р«г — начало РР тогда и только тогда, когда !е— начало Р. В следующих двух теоремах речь идет о началах соеди- нения двух слов. 4.12. Всякое начало слова Р«! либо является началом Р, либо имеет вид РР, где Р— непустое начало Я 14.5, 4.! 11. 4.13.
Всякое начало слова РС7 либо является собственным началом слова Р, либо имеет вид РР, где Р— начало !е !4.5, 4.111. Аналогичные высказывания могут быть доказаны для кон- цов соединения двух слов. 4.14. Пустое слово является единственным собственным началом однобуквенного слова 14.4, 2.3, 2,2). 4.15. Всякое непустое начало слова «Р имеет вид рг, где (е — начало Р !4.13, 4.141. Очевидно имеем следующие два верных высказывания: 4.16.
Слово Р является началом слова РЯ. 4.17. Никакое слово не является собственным началом са- мого себя. Лщко доказывается 4.13. Если Р— собственное начало Я, а 9 — начало Р, п«о Р— собственное начало Р !917.6.2, э'17.5.21. 4.!9. Если (г — начало яе началом Я !4.!8, 4.17!. 5.
Просматривая спис о яснить, имеют ли эти слов говорить, что слова Р и ществует непустого слова а и Я. 5.1. Предикат «Х и У взаимно просты слева» тся собственным в, мы сможем выначало. Мы будем слева, если не сучалом как Р, так разреи8им Р=Л, 5 .-Р, Т Л, мы видим, что условия, налагаемые на Р, 5 и Т, выпол няются при Я хЛ [5.2!. Допустим, что слово Я правильно, и докажем, что тогда правильным будет и всякое слово !~Я, где $ — какая-нибудь буква. Вместо «Х и У взаимно просты слева» мы будем иногда говорить «Х взаимно просто с 1' слева», 5.2.
Пустое слово взаимно просто слева со всяким словом !2.31. 5.3. Если $~Г11, то сР взаимно просто с т)!г [4,15, э 17.4.2!. 5.4. Если $»ь»1, то КР не является взаимно простым слева с т1(). Это непосредственно следует из определения взаимной простоты слева. 5.5. Если Х взаимно просто слева с У и Уф Л, то Х взаимно просто слева с У$ [5,2, 5.4, 5,3), Докажем теорему 5.6. Каковы бы ни были слова Р и !',1, могут быть построены слова Р, 5 и Т такие, что (1) Ря.Р5, (2) Я хРТ и что 5 взаимно просто слева с Т. Фиксируем слово Р.
Будем говорить (на время этого до. казательства), что слово 9 правильно, если осуществимы слова Р, 5 и Т, удовлетворяющие условиям (1) и (2) и такие, что 5 взаимно просто слева с Т. Требуется доказать, что всякое слово (в рассматриваемом алфавите) правильно. Пустое слово Л правильно, так как, полагая по определе- нию ч Р,=Р, 5,=5, Т, =Т5 во С ЕМ И ОТНКА 1гл. и По определению правиллйости могут быть построены слова )7, 5 и Т, удовлетворяющие условиям (1) и (2) и такие, что 5 взаимнол(росто слева с Т.
Если окажется, что ТдЛ, то 5 взаимно просто слева с Ть [5.5), и, полагая по определению. (3) (4) (5) мы видим, что (6) х Р„5, [(1) (3)* (4)! (7) б!5кК,Т, [(2), (3), (5)! и что 5, взаимно просто слева с Т,. Таким образом, в дан- ном случае слово 5)5 правильно [(6), (7)], Пусть теперь (8) ТАЕЛ. Имеем тогда (9) д х р [(2), (8)!.
Если 5мЛ, то 5 взаимно просто слева с ь [5.21, и, пола- гая по определению (1О) (11) 5„— Л, (12) Т,= — $, мы видим, что имеют место равенства (6) и (7) [(1), (10), (11), (2), (8), (12)! и что 5, взаимно просто слева с Т,. Таким образом, и в этом случае слово Я$ правильно.
Наконец, если 5:)ГЛ, то существуют ~) и 1' такие, что (13) 5 о т)Р Если здесь т1хе$, то имеем (14) [(2), (8)!. и, полагая по определению (15) (16) 5, =1~, (17) Т,=Л, мы видим, что соблюдаются условия (6) и (7) [(1), (14), (13), (15), (14), (17)1 и что 5, взаимно просто слева с Т, [(17), 5.2!. Следовательно, 1е$ правильно. % гв1 НАЧАЛА Н КОНЦЫ СЛОВ 81 Если же 0 ф"„то также имеем (14) и, полагая по опре- делению (18) И,=Я, (19) 5 — т~у, (20) Т, 5, мы видим, что соблюдаются условия (6) и (7), !(1), (!4), (13), (18) — (20)! и что 5, взаимно просто слева с Т, [(19), (20), 5.3!.
Следовательно, Я правильно, и теорема 5.6 доказана. 5.7. Если соблюдены условия (1) и (2) и 5 взаимно просто слева с Т, то всякое оби!ее начало слов Р и Я есть начало сло- ва Р !4.12, в 17.5.2!. 5.8. Каковы бы ни были слова Р и Я, существует единствен- ная тройка слов Р, 5 и Т, удовлетворяющая условиям (1) и (2) и такая, что 5 взаимно просто слева с Т 15.7, 3.4, в 17.5.21. Каковы бы ни были слова Р и Щ слово )с в единственной тройке слов )т, 5 и Т, удовлетворяющей условиям (1) и (2) и такой, что 5 взаимно просто слева с Т, мы будем называть наибольшим общим началом слов Р и 1е.
5.9. Каковы бы ни были слова Р и 1е, существует единствен- ное наибольшее оби!ее начало этих слов !5.8!. 5.10. Всякое общее начало слов Р и 1;! есть начало их наи- болыиего общего начала !5,7!. 5.11. Всякое начало наиболыиего общего начала двух слов есть их оби!ее начало !2.4!. 5.12. Слово !с тогда и только тогда есть общее начало слов Р и 1Е, когда оно есть начало их наибольшего оби(его на- чала !5.10, 5.11!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
