# connectivity in automata by words of length n-1

Let $A$ be a complete strongly connected automaton with $n$ states. Does always exist a word $v$ of length at most $n-1$ such that its underlying graph is connected? That is for any pair of distinct states $p,q$ exists a positive integer $k$ such that either $p.v^k = q$ or $q.v^k = p$. Additionaly we can assume that there exists a word $w$ such that its underlying graph is connected.

The statement also can be reformulated in terms of linear algebra.

-
The automaton is deterministic. Right? – Mark Sapir Apr 3 '12 at 18:26
>The automaton is deterministic. Right? right – Misha Berlinkov Apr 3 '12 at 18:26
There are some other assumptions missing otherwise the answer is obviously "no", see my answer. – Mark Sapir Apr 3 '12 at 18:43
The assumption is "Additionaly we can assume that there exists a word w such that its underlying graph is connected." and we can also assume that $w$ takes $A$ into one state, but I think it is not necessary. – Misha Berlinkov Apr 3 '12 at 18:55
Assumption that $|Aw|=1$ implies that the GCD of the lengths of cyclies in $A$ is 1 (see Trakhtman's theorem). Perhaps you should reformulate the question putting the necessary assumptions before the question itself. The question should say something like: If there exists $w$ for which $(A,w)$ is connected, then there exists such a $w$ of length at most $n-1$. – Mark Sapir Apr 3 '12 at 19:07