АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП И ИХ ПРИЛОЖЕНИЙ 1983 г.

,„Дпя доказательства утверадения ( 6 ) нужно рассмотреть два случая. Случай I . k = l - I , l ? j . Тогда и, следовательно, по п. ( с ) леммы Г буква G 4.-4 - начальная буква слова Ct,м . . . G { R , а тогда по п .,(в) этой же леммы С 4 т б для некоторого Й^сЕ'Пп-м . Завершаем доказа­ тельство случая I применением индуктивного предположения относительно равенства G4 4.4 ••• Q т G.^ -4 61i. »•. R 4 утверждения ( 6 ) . Случай 2. k ^ t - I , ( > } . Тогда 'Здесь Ctfc коммутирует в Пам с нитью и, следовательно, по п .(в ) леммы Г для некоторого имеем 6 ) =G(. &i* Завер­ шаем доказательство применением индуктивного предположения относительно равенства Qi . . . й д С ?4 r^k+ 't • утверадения ( 6 ) . Пусть выполняется равенство (5 ) . Если k * i , то ai a iM . . . Q | Q = O iQ t -4 и , следовафельно, по п .( а ) леммы Г сць| ...Q ^ < 3 т О ы . . . б ч к . Легко видеть, что i- 4 ,< ? и по п. (в) леммы Г найдется такое положительное слово -£ , что G) , а это доказывает утверждение (7 ). Утверждение ( 8 ) доказывается аналогично. Докажем ( 9 ) . Мы имеем в Пп +1 G^ . . . Gj* Q т Q 4 - 4 Q 4-2 •••Gt ft Докажем, что буква является начальной буквой в олове (Н ...О|<о} тогда и только тогда , когда Q г cii- 4 C ii ...o }Q i . Если Q = a iiQ i ...a j(s b , то ( Q i < W .. o j j G i - .G i . . . ? (a < ^ O i...c ip G i4 Q j... Q* и <Н- 4 - начальная буква слова C ^ ...O tQ . С другой сторо­ ны, если a 4 , - начальная буква в слове сц ... . cij< 3 , то по п» ( с ) лемш Г 0;.-4 является началом слова а - ^ а ^ г ...G^CJ. Так как a b t a i M Q ^ . . . a j тСДм Сц,г ... й . } С ч -<1 , то по п. (в ) Деммы Г - начало слова Q и, следовательно, б ? » > 0 ^ 8 . - 47 -