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

-аво- В. А. ГРИГОМ К ПРОБЛЕМЕ ПРИМЕНИМОСТИ ДЛЯ НОРМАЛЬНЫХ АЛГОРИТИОВ Рассматриваются нормальные алгоритмы в произвольном фикА скованном алфавите & ; схема которнх имеет вид: А , - * 6 , О) Проблема, распознавания применимости формулируется следующим образом. Для любого слова \У в алфавите & определить1, применим ли алгоритм А 1—^>Ь1 к слову У / . Для некоторых классов нормальных алгоритмов вида ( I ) решается проблема рас­ познавания применимости. Еак обычно, через &\У/) будем обозначать длину слова V/ , У/'*, № п означают соответственно левую и правую части слова \Х/ . Пустое слово будем обозначать А . Знак 2 означает графическое равенство, А £ В означает, что слово А является подсловом слова В . Если У/ и V два слова и V получено из ^ одно­ разовым применением нормального алгоритма А , — ’ 'В* , то буцем обозначать это V . Знаком \ Л / \ / будем обозначать, что слово V получено из слова V/ применением К раз (/<>•• / ) нормального'алгоритма А1~^В1 . Если не существует такого слова X ; что А ж А ' Х И В гХ В ' , то будем записывать это так': А Л 8 ^ А в противном случае Д А В Ясно, что если С-(АЛ)> 1(В^ то нормальный алгоритм всег да применим. Если ¿(А,)~ 1(£я) , то проблема распознавания применимости легко разрешима. Действительно, так как в сего различных слов длины ¿ (У / ) будет