Разрешимость
Это разрешимо. Есть только конечное число возможных функцийf:Q→Q, так что вы можете смоделировать это как проблему достижимости графа, с одной вершиной на функцию и ребром g→h если существует a∈Γ такой, что h=fa∘g, Затем, проверяя, является ли функцияg в G сводится к тестированию g достижим в графе от fϵ, Вы можете найти самое короткое такое слово, используя ширину в первый раз. Время выполнения может быть экспоненциальным вQ, хоть.
Длина слова
Самое короткое такое слово может быть экспоненциально длинным. Вот пример такого DFA. Позволятьp1,…,pk быть первым kпростые числа. Тогда состояние будет иметь вид(i,x) где i∈{1,…,k} а также xi∈{0,1,…,pi−1}, Определите DFA с одинарным алфавитомΓ={0} и функция перехода δ((i,x),0=(i,x+1modpi), Функцияf0:Q→Q дан кем-то
f0(i,x)=(i,x+1modpi).
Теперь рассмотрим функцию g:Q→Q дано
g(i,x)=(i,x−1modpi).
Можно использовать теорему об остатках в Китае, чтобы показать, что g=f0n где n=p1×p2×⋯×pk−1и что 0nсамое короткое такое слово. Более того,|Q|=p1+⋯+pk, так n экспоненциально велик в Q,
Следовательно, нет никакой надежды на алгоритм полиномиального времени, который выводит такое слово. Это все еще оставляет открытой возможность использования алгоритма полиномиального времени дляg в G, хоть.