НГУ
http://forum.nsu.ru/

Разрешима ли эта задача (про перезапись слов)?
http://forum.nsu.ru/viewtopic.php?f=24&t=22903
Страница 1 из 1

Автор:  AGu [ Вс дек 11, 2011 10:09 pm ]
Заголовок сообщения:  Разрешима ли эта задача (про перезапись слов)?

Рассмотрим какой-нибудь алфавит и функцию ,
определенную на конечном подмножестве .

Продолжим на , полагая ,
где -- самый длинный префикс слова , принадлежащий .

Положим .
Т. е. -- это множество бесконечно переписываемых слов:


Существует ли алгоритм, который для данных и
выясняет принадлежность ?

P.S. Ответ я знаю, но я его получил муторным кустарным способом.
Не сводится ли эта задача к чему-нибудь хорошо известному?

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/