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

следует, что слово В 1ш является началом некоторого определя­ ющего олова и выполняется одно из условий: 2 .1 . X , &i m W - определяющее соотношение; 2 .2 . Ъ т„ &c„t , s Ь1т W и существуют определяющие соот­ ношения вида Й<*,+,- = Н , Н - в ; ы ^ . Итак, у нас имеется определяющее олово XtK, B-tm , подслово Xim S • определяющего сл о ва, причем слова Xt„ , 8,-„ , S непустые и I - начало слова . Поэтому в любом из слу­ чаев 2 » 1 , 2 .2 мы можем применить условие Т /& ) . При этом по- Лучим:__ Xtn * £ < v « Yi^-i X i n i т . е . слово К * . , пусто, и й<*г K » .f А , . , * Из ( д ) теперь следует: — * < „ .,2 У{4...У(т.г (заметим, что из пустоты *» *-« следует f» ) . Отсюда из Дей&м 1 и из соотношений к ж„ ^ с , = x im B im получаем Х ц . . . X iM4 B i „ „ * К , Ф с щ - « г ^ - П „ _ г 4 * н *> , . . . Я * . Снова, как и р ан ее, из доказательства леммы 1 имеем, что либо Х'ы В с * * W - определяющее соотношение, либо . **'т &*». * &**•* V * где W *• некоторое непустое сло во . Из последних соотношений следует Xi\ •»-> Ж£* -1 &i я, • Получили противоречие со следствием 1» Таким Образом, л еш а 4 верна при i = у . Пусть лемма вы­ полняется дум i - К , К > у . Тогда . . . /?*-< = Хв 1~1 . . . . Кроме то го , из ( 7 ,8 J следует, что s ('иначе придем к Противоречию со следствием 1 , т .к . S * = 7^ по лемме 1 ) . Сле­ дователи о , равенство ( 6 ) выполнено и при / = К + f ; равен ства (7,8) доказываются точно так же, как и при 1 ~ 7 . ) Лемма 4 д о казан а. Назовем порождающее множество подполугруппы Н непри­ водимым, если никакое его собственное Подмножество не порожда­ ет Н . " ЯЁ й МА 5 . Пусть П - полугруппа, в которой каждой слово равно конечному числу различных сл о в. Пусть Н - под­ полугруппа в П , заданная каким-либо конечным порождающим 79