АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1981 г.

Рассмотрим теперь полугруппу П * ~ < а Г ~ * , а с г-м, > Каждое слово в этой полугруппе будет плеть вид: ( 2 ) a . е / а е£/ ■a ef*a ef‘ K+ f с с б *+z где каждое С. - 6 в ^ шш с,- = с г ' ^ Так как /7* является подполугруппой полугруппы П а , то она тоже не содержит свободной подполугруппы ранга 2 . Следователь­ но, среди слов вида 2 имеются равные (но не тождественно). Тогда, взяв любое подслово из слова вида 2 и считая его опре­ деляющим, легко полазать рассуждениями, аналогичными рассуж­ дениям в лег,иле 2 , и индукцией по длине слова, что любое определяющее слово разбивается в два нормальных, а это проти­ воречит определению класса Кг . Следовательно, предположение о существовали! трех образуюсих пр!шодит к противоречию. Значит, рассматриваемая полугруппа может плеть только два образующих. ЛЕША 4. Полугруппа По имеет задание no^<(xJ J Из лемгл: 2 следует, что определяющие слова слоговой длины два имеют вид: о / 4 ^ и , <^>1, </>-/ . Предположим,что существуют определяющие слова большей слоговой длины. Рас­ смотрим полугруппу, порожденную элементам! < $ 1 x 8 ^ Так как она не свободная, то существует определяющее слово вида 8 S 0 i 8 i ( t > o S > о ) . Легко видеть, что если f > S , ^ t , то слово / а 6 разбивается на два нормальных. Если же § , то слово о а. разбивается на два нормальных. Предположив, ч т о , полу­ чим, что слово оР '4 в разбивается на два нормальных. Следо­ вательно, o L - i или с ? - / . Аналогично можно доказать, что или / '- - l . Если об=/ и /*=•/ , то а,°с^.>3 разбиваете на два нормальных. Если , то 8 ^ 0 ,^ раз­ бивается на .два нормаль,пк. Следовательно, =6 =J~=i и опре­ деляющие слова слоговой длины 2 имеют вид ol f t 8 c l (^~>1 </>■/) Если существуют другие определяющие слова, то шш содержат а. 4 иля 8а. , и поэтому a £ fi или 8 а / будут в зб и в а т ь с я на два нормальных. Отсюда заключаем, что существует единственное определи- - 128 -