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

неизолированное подслово v~t в множестве S- i g ig - iJW’ и - ПОДСЛОВО trt t ^ /1+1Ъ 1 . Вое элементы >, из (5J ввда: у 4 t=9 ld c 9 " заменяем соответственно на ^ Удалив из полученного множества / tr^ ii= fj( пустые сло­ в а и оставив все различные слова, получим множество /££'У/. f/R, к . Упорядочим его: г;* * ггя " £ ... п т " , . ( 6 ) Аналогично из множества S элементов рада (3) выделим элементы л,- , начинающиеся на д , и заменим их произведе­ ние!,! ^rt ' /Sl irt =£■ , то есть изолируем подслово д слова г£ в множестве S . Удалив из преобразованного множества { S/J элемент Q если он в нем содержится, и оставив различные элементы ( получим множество 3 " , уиорадочив которое, будем иметь ряд: S?*SZ< ... ( 7 ) Непосредственной проверкой убедимся в следующем: с ) из того, что 5,"= .. x~'(rt ) a x t (r\ ) .. x t O) принадлежит (7 ), следует, что подслово i£ Y /A ..-г/ являемся начальным подсловом некоторого е =* у ,где ig " принадлежит ( 6 ), и X;*(i)C3*t (D, , У,' '(i't <)О *t (rt 4 ), ,x t U) являются элементами ряда (7 ); и ) каждое слово г^" или V ^ из ( 6 ) обладает свойством <* пли (S относительно ряда (7 ). б А. Если первое слово £ £ - х (1 )... x ( i ) x ( t + /) ... * ( rt ) из ряда (5) со свойством р длины L(bt ) =Z t имеет неизолиро- Ешнше относительно S левую и правую половины, то изолиру­ ем Х(Ч) . x (i) в множестве / l ~ ij< и в множестве 5 указанным нише способом. Для полученных в результате преобра­ зований множеств составим, как в А , упорядоченные рады (С) и (7 ). • 8 }- Заменяем ряд (5) рядом ( 6 ), рад (3) - рядом (7 ). Применяем к радам ( 6 ) и (7) преобразования A t , <’* 1, г, и в Увязанной пыле последовательности. (невидно, через конечное число шагов множество^ будет преобразовано в ни.тьсенозское IV , а ряд (3) ■ во вон л I.тигельный ряд ( 4 ) для W / 6