markov_teorija_algorifmov (522344), страница 66
Текст из файла (страница 66)
Левая [и [ разия) часть соотношения содержит одно и только одно вхождение оперативной буквы. 1.3. Буква я либо не входит ни в левую, ни в правую часть соотношения, либо входит по одному разу в обе части. В пос- леднем случае либо обе части начиншотся этой б ", б оканчиваются ею. я это уквой, либо обе Из 1.2 и 1.3 вытекает 1.4. Всякое слово, смежное в 43 с каким-нибудь специаль- ным словом, само есть специальное слово.
Отсюда в силу 3 57.6 следует 1.5. Всякое слово, эквивалентное в 6 какому-нибудь спе- циальному слову, само есть специальное слово. Пусть Р— слово в алфавите В. Условимся гово ить, что слово 9 смежна справа со ело Р, вом, если О может быть ь »8! ИБРАЗРешимое АссоцилтивнОе исчисление 333 получено из Р в результате подстановки правой части одного из соотношений системы (3) вместо какого-нибудь вхождения левой части этого соотношения. Для обозначения смежности справа будем пользоваться знаком «)-». Запись Р )- г,"г будет в дальнейшем означать, что 9 смежно справа с Р. Из сравнения определений смежности слов в ассоциативном исчислении (2 57.5) и смежности справа непосредственно очевидна справедливость следующего утверждения: 1.6.
А): РлЯ тогда и только тогда, когда имеет меспго одно из двух; Рг-(г или 1г )- Р. Докажем следующую лемму: 1.7. Со всякилг специальным словом смежно справа не более чем одно слово. Для доказательства, очевидно, достаточно установить, что во всякое специальное слово входит не более чем одна из левых частей соотношений системы (3) и не более чем один раз, Рассмотрим какое-нибудь специальное слово Т. Согласно определению Т я. ПЯ»1гся, где 9 и )7 — некоторые слова в А,  — оперативная буква. Возможны два случаьр г) есть одна из букв р; (1<1<У); г) есть одна из букв а; (1«<У+1). Рассмотрим их порознь.
а) Пусть г)Хр. Так как огЗСру (1<»<У+1), ни одна из левых частей соотношений 5-й и 6-й групп не входит в Т. Так как ргф:р~ при г~), из числа левых частей соотношений первых четйрех групп в Т могут входить лишь р2$Х ($ — буква А; Х вЂ” слово в А; [СХэ =1; $Х~1'(г' ), Р,Хп (Х вЂ” слово в А; [Хг <1), Р (77.
Слово Р (72 входит в Т лишь тогда, когда 1« начийается словом (7, Слово вида р~$Х($ — буква А; Х вЂ” слово в А; [$Хв = 1; $Х~1'(7 ) входйт в Т лишь тогда, когда В не начинается словом (г и [ггг) 1; в этом случае лишь одно слово указанного вида входит в Т вЂ” то, для которого сХ есть начало длины 1~ слова )с. Слово вида р Хя (Х вЂ” слово в А; [Хе <1) входит в Т лишь тогда, когда [В (1г, в этом случае лишь одно э l слово указанного вида входит в Т вЂ” то, для которого Х аАгт. Так как эти три случая попарно несовместимы, в Т входит не более чем одно слово рассмотренных видов. Единственность его вхождения в Т очевидна. б) Пусть «1хар Так как ргл1'а~ (1<1<У), ни одна из левых частей соотношений первых четырех групп не входит в Т.
Что касается остальных соотношений, то прн 12 А, А. Марков, Н. М. Нагорав» ПРОБЛЕМА ТОЖДЕСТВА ДЛЯ ПОЛУГРУПП [ГЛ. ЧП1 4 Бе) НЕРАЕРЕшиМОЕ АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ 555 354 Ям.Л и 1<1< Ф в Т очевидным образом входит левая часть па )ьго соотношения 5-й группы и только один раз, тогда как левые части соотношений 6-й группы и других соотношений 5-й группы не входят в Т; при Я м. Л и )*=У+1 в Т вообще не входит ни одна из левых частей соотношений системы (3); наконец, при Я„е.Л в Т входит левая часть $а~ одного из соотношений 6-й группы, входит только один раз, левые же части других соотношений 6-й группы и левые части соотношений 5-й группы не входят в Т.
Этим лемма доказана. 1.8. Если Я вЂ сло в А, то никакое слово не смежно справа со словом паЯП. В самом деле, ни одна из левых частей соотношений системы (3) не входит в слово пон+1ЯП, т. е. в поЯп. В-ряд 5 'мы будем называть правильным, если правая смежность Х)-Г имеет место для любых Х и )' таких, что Х соседствует слева в 5 с )'. Будем говорить, что Р собственно преобризуемо в Я, если может быть построен правильный В-ряд 5, соединяю- щий Р с Я и такой, что 15о) 2*).
Будем говорить, что Р преобразуемо в Я, если Р собст- венно преобразуемо в Я или РйЯ. В дальнейшем запись Р)-Я будет означать, что Р собственно преобразуемо в Я; запись Р)= Я будет означать, что Р преобразуемо в Я. 1.9. Если Р и Я вЂ” слова в алфавите А такие, что имеет место эквивалентность В: прРП )) поЯП, то прРП( поЯп. В самом деле, пусть выполнено условие леммы. Тогда существует В-ряд 5, соединяющий пррп с поЯп. Так как о'31.'р, то 15о)2. Пусть Х соседствует в 5 слева с поЯп.
Тогда, согласно 1.6, Х)-ПОЯП или поЯп(- Х. Но в силу 1.8 поЯп )- Х невозможно. Следовательно, (4) Х )- поЯп. ) См. 4 24.4. Если для любых слов 1' и Е таких, что )' соседствует в 5 слева с 2, (5) у~-г, то 5 — правильный В-ряд, и по определению собственной преобразуемости прРп)- поЯП.
Допустим, что в 5 имеют место не все правые смежности (5). Используя теорему о наименьшем числе, мы без труда построим В-ряды У и К и слова с и )' такие, что (6) 5 Аг У)'ус)1„ (7) 2) — )' и В-ряд уЛт является правильным. поЯп является последним членом 5, а потому и уЛ~. Кроме того, легко видеть, что У~ГПОЯп 1(7), 1.81, Следовательно, В-ряд у' непуст. Пусть Т вЂ” первый член 11. Тогда (8) рхутг, (9) 5 Х(7УуЬ~ТУ' ~(6), (8Ц и (10) г >- т.
Первый член В-ряда 5 является специальным словом. Поэтому все члены 5, в том числе и 2, специальны (1.51. Отсюда, на основании 1.7, мы заключаем, что (11) )'Х Т ((7), (10)1. " Следовательно, 5 я (7туЪутУ' ~(9), (11)1, и потому система 5,= иту, являющаяся, как легко видеть, В-рядом, также соединяет прРп с лаЯл. Но ~5о ~5о+ 2 Таким образом, мы заменили В-ряд 5, соединяющий прРп с поЯП, более коротким рядом 5,.
Если этот ряд еще не является правильным, то, действуя аналогично предыдущему, мы заменим его еще более коротким В-рядом 5„ соединяющим прРП с поЯп. Повторяя этот процесс последовательного сокращения .ряда, мы, наконец, придем к пра- 12о пРОБлемА тОждествА для полуГРупп !Гл. ун! вильному В-ряду, соединяющему прРи с поЯи, и тем самым установим, что ирРи ~- по!'1и. Лемма доказана. Очевидным образом имеем 1.1О. Если Р(-!г, то В: Р ~[1г. ! .11.
Пусть 5 — правильный В-ряд, первым членом кото- рого является 1«', а последним — иовгп, где (1 — слово в А. Тогда всякий правильный В-ряд с первым членом %7 явля- ется началом 5. В самом деле, пусть выполнено условие леммы. Тогда в силу 1.6 слово %' специально и всякий В-ряд, начинаю- щийся словом %', состоит из специальных слов. Для дока- зательства заключения леммы мы воспользуемся методом индукции по построению правильного В-ряда. База индукции тривиальна: ряд у)уу действительно яв- ляется началом 5. « Пусть теперь 5, †правильн В-ряд с первым членом й7 и последним членом Х; пусть (12) Х [ — У.
Покажем, что если 5! Является началом 5, то этим же свойством обладает и 5,Уу. «;9 Итак, предположим, что 5! является началом 5. Тогда (13) 5Х5«Р для некоторого 11. Кроме того, (14) 5«х5,Ху, где 5,— некоторый правильный В-ряд. Отсюда (16) 5« ~. 5ау для некоторого 5„и потому (16) 5Х5,уХуж [(13), (14), (16Ц, Легко видеть, что Р~Л, так как в противном случае было бы 5 аь 5вуХу [(16Ц и Х а- по!чи, что в силу 1.8 противоречит (12). $ вв1 неРАЕРешимое АссоциАтивное исчисление 357 ир«ри 1- по«+ври, н потому пр;Рп ~ пов+вРи. Пусть теперь [Рг)~ 1а, Так как (7! не входит в Р, имеем 17! ~ГЛ и, значит, 1! > О.
Поэтому в данном случае Р.7г Л. Возьмем слова 1г н 1«такие, что (20) Р «1«'11 и (21) [Рг = 1.— 1 П сть буква $ и слова У, 2 таковы, что 1г л. Уэс. у Тогда й2йг ) 1; [(21Ц у1« есть В-ряд. Пусть с — первый член этого ряда. Тогда (17) уУ Хулу)У, для некоторого 1«!. Отсюда (18) 5Х5вуХуЕу1!вв [(16), (17Ц, 1 и, так как 5 — правильный В-ряд, Х 1- 2 [(18Ц, что вместе с (12) в силу 1.7 дает (19) гХ У.
) Следовательно, 5 Х 5ауХуУуй! И18Ц Х5,Ууй, [(16), (14Ц. Таким образом, В-ряд 5,Уу действительно является началом ряда 5, что и требовалось доказать, 1.12. Если слово (7! не входит в слово Р в алфавите А, то ир; Рп ~ ио;,,Ри. В самом деле, если [Рг < 1О то соотношение рвРп а-во!ч Рп принадлежит 2-й группе соотношений системы (3). Следо.
вательно, тогда ззз пРОБлемА тождестВА Для ПолуГРупп [гл. Тпп н $с)г не начинается словом Уг. Следовательно, в (22) и)'р192ггп входит слово вида р!БХ, являющееся левой частью одного нз соотношений 1-й группы системы (3). Применяя к слову (22) допустимое действие исчисления В, соответствующее этому соотношению, получаем (23) п)'рдгВ >- п)'~р,г)7 . Теперь, используя (23) для индукционного перехода, мы без труда, обычным применением метода индукции можем показать, что (24) прг г',! яп ~1 и Яр!!сп. ' В силу (21) соотношение р!Яп++ о;+!ггп принадлежит 2-й группе соотношений системы (3) и, значит, (25) пЯргггп ! — ПЯП!+!Яп.
Принимая, наконец, во внимание соотношения послед- ней группы системы (3), без труда индукцией получаем (26) пао!.,В Ьпо!.!Е)~ . Таким образом, пргРП !- ПЯр!ггп [(20), (24)] !- и!',го!+Яп [(25)] ~- по; „Дйп [(26)] 7дпа;„Рп [(20)], что и требовалось доказать. 1.13. Если ни одно из слов У, (1<! <й — 1; А<У+1) ие входит в слово Р в алфавите А, то пр,Рп 1- падРп. В самом деле, при этом условии (27) пргРП ~ паг„.,Рп (1 < ! < й) [1.12]. Кроме того, в силу соотношений 5-й группы схемы (3) (28) по!+„Рп ( — пр;+,Рп (1 < ! < lг — 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
