Ученые записки математических кафедр вып. 1970 г.

№ ) . П \ где п. - число букв в алфавите Яг \ то применяя нор­ мальный алгоритм ( I ) к слову молен получить два случай! 1) Алгоритм применим к слову и / Не больше, чем раз. то есть в этом случае нормальный алгоритм применим к слову IV 2) Алгоритм применим к слову IV больше П 1 М раз. Тогда в це­ почке должны встречаться два одинаковых слова. Следовательно', в этом случае нормальный алгоритм не применим к слову V/ Значит, интерес представляет случай, когда * Ясно, что если слово А 1 содержится в В, * то проблема приме^ нимоств легко разрешима. Предположим, что А<ф В< . Возможны подслучаи: а) ^ Л В . л Л ■ В1ПА, ' Л Т~ (1 ) будет пРи“ ени" к лобому слову IV не более ^ раз’ где [ 3 знак антье. Также легко видно, что 6 СЛй! Ю В1 ЛА1 х а ■ А, ЛВ, У А в) в, П А 1 / Л или и А, п в у Г А И, то нормальный алгоритм вила Гт') и« - ритн вида и ; всегда применим. Рассмотрим случай, когда А, Л 8 ^ Л * Ь Л А , ф А Д .К ..С » 4 , « , . ц , « , . д а ч , ™ . .МГЧЩП1 з м а и с , ■ выполнены условия:- г.' с.юм - к .*;> ^-:У гл I. А ф:Ь. 12 » йуквя р ^ 4 ( е<^,е одного р а з а ;л я гакаа*-Что а в х о д и т ь В Не