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

1 огда бЦО^М •• 1 = Q\Ol м ..• 0 ‘^ 0 \ а £> = ••. 6 ?j S* и по п , ( с ) лемш Г для т о г о , чтобы была начальной в бЦ необходимо, чтобы буква а<. была начальной в слове Q v h . .. О .й и по индуктивному предположению для не­ которого Qt в ППм S и, следователь- 40 9 Q . Таким образом, им?ем в Пп-н <ЧСци •••Q jQv-iO t •** 6 ijQ^ е Qt--( 6 } i -2 ••*бН&т .с^ а -^ сч ‘ ••Q.yiQi И, следовательно, •••Q -4 Q i •••O j ) т 61{. - 2 . По утверждению (8) существует такое слово Т , что 61 а ••• г Oi -2 •••сцТ R г ( ла ••• X Здесь + 3 ( 0 ^ .. .Qt) +3<Я,+ЭТсс5 и поэто­ му по индуктивному предположению и,следовательно, 0 G j l r O i - v aj-Q t - 2, j -i € i г ... t t y + l - l и Ъ * _ ^ •)>•. £ l j 4 - k 2 . R r ? f u , £ h ,J"U.. ft ,}K -k -i 2 . что и требовалось доказать. На рисунке 4 показан частный случай утверждения ( 9 ) C^ 050 ( j GJ • Q^O-gCX^ R Рис. 4 Докажем утверждение f lO ) . ItycTb k = t +1. Тогда О А' ••6*^(5} ^=Cl^w|Q^ •. • R - 48 -