Рассмотрим какой-нибудь алфавит и функцию ,определенную на конечном подмножестве . Продолжим на , полагая ,где -- самый длинный префикс слова , принадлежащий .Положим .Т. е. -- это множество бесконечно переписываемых слов:Существует ли алгоритм, который для данных и выясняет принадлежность ?P.S. Ответ я знаю, но я его получил муторным кустарным способом.Не сводится ли эта задача к чему-нибудь хорошо известному?
| 
Линейный вид
