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

с е в некоторое подслово слове £ * из обеих частей равенства ('как в лемме 2 ) . При этом тип каждой буквы иа Я -сегментов можно определить как пару (а не четверку J чисел (Щ , , т .к . по лемме 4 /Vj - А/, , л /к =fi/t для любой такой буквы. Ясно, что полученное после выбрасывания подслов соотношение будет снова нетривиальным. 2 .2 . Пусть общая длина Я -сегм ен то в не более, чем £■£ , Тогда суммарная длйна X -сегм ен тов в Е Л додана быть больше Z t L M i C t , По лемме 4 для каждого X -сегм ен та ив Е л запишем! а ) Я(< . . . Ж(/ в . . . К / или б) Х;4 . ■ ■ Х,у — ... £ у Если выполняются оба эти соотношения, то примем во внимание только а ) . Назовем выделенной буквой последнюю^букву сегмента X{j в случае а ) , и последнюю букву слова Х,у в случае б/. Если сегмент пуст, то выделенной будет последняя буква преды­ дущего сегмента,. Заметим, что между двумя оосбдниш выделен­ ными буквами, входящими в олово Щ ‘ ‘ * '" * % < содержится не более С невыделенных букв - это следует ив леммы 4 , Между соседними выделенными буквами, одна из которых находится в конце сло ва Х , \ Xt‘t , а другая - в олове дрц# тоже содержится «о более С невыделенных букв йа X - с е г ­ ментов. Тогда в £ * й о д а т больше, чем g i L H ' c выделен­ ных букв. Типом выделенной буквы А ^ назовем шестёрку чисел (N i t • • • , N g ) , где Nff A 't внять равны номеру обраеуида* г о Щ и номеру места в нём, к а Котором стоит буква j A/i принимает значений 1 или 3 в йанйсймооти от ТОГО, какОй случай имеет место - &) turn б Ц &V и Я'г » ооотаетствекио номера сегментов и в яаяум ер о^нмм множества под­ слой овр^Дёлйядах слов» - д ли н е Щ а оДучев Й|, дабо дайна fy - в случ ае б ) , В сего ймеётся на болей различных типов выделенных букв, Следовательно, в 0 * . сумвс- твую» хо тя бы двё выделенные буквы о- одинакова* типом. Йенс, что после в ы б р а с ы в а я соответствующего педелойа • i f '* в обеих частях ( 11 ) мы вновь получим нетривиальное соотношение между образующими подполугруппы Н , - нетривиаданость ораву следует йз определения типа и леммы 4 , а доказательство ра­ вен ств а левой ж правой частей легко сводится к случаю, рассмо- 82