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

будет ля W , дельта словом. ОШАЛ 2. 2у0La-к,La~7,¥ О, 2уа1о-каЬ0-ча *0. Тогда п = т =Ст , где . Так как П Z т , то 0 * 1 . Если С = 1 , т о п - т и уравнение (14) имеет вид Wz n = W , m , (15) и вопрос свелся к рассмотренной вш е задаче для полугрупп. Заметим, что если ' Тб) имеет решение, то и уравнение ( I I ) имеет решение, если уравнение (15) не тл еет решения, то и ( I I ) решения не имеет. Воли С>1 , то подставляя в (14) п =с т 1 имеем: д З к С е - П г г ц ^ Если С е T t г то (16) преобразуем следующим образом № • < * - 4 /а Г = ( Й / Д Г (17) Вновь решение уравнения ( I I ) свелось к решению уравнения (17) в полугруппе Q + . Если с е / ? т . е . То п = ^ т и r i = q t , m = p t . Подставляя п и т в (14), получим: a W w - p * ) 1 - ( $ / < * ) * Откуда: (18) Так как олова положительные, то решение уравнения (14) свели к решению уравнения (18) в полугруппе Gr* . СЛУЧАЯ 3. 2 у 0 La - к , L „ - i , = 2 y 0L0 - к л L„ -?* =О . откуда /(<4,+7, L a , Т . е . L ( w , ) - - L(wt i); /V тате как VV, = 1Л* W, , то перепишем уравнение (14) в виде: А * * (П-т ) « Г ' ’) п ~т = ( % 1 \ Т . (19) f*-* г~* В Ш 21. Пусть ' W , -положительное слово. W, дельта - ю в о тогда я только то гд а, когда с у ествует я V I г ( w , y e <4*>.- о iuKA.3A.TEJIЮТБО. Действительно, если VV^ - дельта слово, - 92