finite state machine is strongly connected

Question

Let M be an n-state reduced strongly connected finite state machine. prove there exists an input string $w$, where $|w|\le n(n-1)/2$, s.t. M assumes each of its states at least once in response to $w$.

Answer 1

HINTS:

1. $\displaystyle\frac{n(n-1)}2=\sum_{k=1}^{n-1}k$.

2. Let $A$ be a set of $k$ states, where $k<n$, and let $s\in A$. There is a word of length at most $k$ takes the machine from $s$ to a state not in $A$.

Added: Suppose that $1\le k<n$ and that we’ve found a word $w_k$ of length at most $\frac12k(k-1)$ that takes the machine through $k$ of the $n$ states of $M$. For $k=1$ the empty word works: after reading the empty word, we’ve been to one state, the initial state of $M$. Let $A=\{s_1,\dots,s_k\}$ be the set of states that we’ve visited in the course of reading the word $w_k$, and let $t$ be any state not in $A$. Since $M$ is strongly connected, there is some word $u$ that takes the machine from state $s_k$ to state $t$. Let $u=\alpha_1\alpha_2\dots\alpha_m$, where each $\alpha_i$ is one character of input. Let $t_1$ be the state reached from $s_k$ by reading $\alpha_1$, $t_2$ the state reached from $t_1$ by reading $\alpha_2$, and so on to $t_m=t$.

Now suppose that some state along the path $$s_k\overset{\alpha_1}\longrightarrow t_1\overset{\alpha_2}\longrightarrow t_2\overset{\alpha_3}\longrightarrow \ldots\overset{\alpha_m}\longrightarrow t_m=t$$ is repeated: $t_i=t_j$ for some $i<j$. Then we can simply delete the segment $\alpha_{i+1}\alpha_{i+2}\dots\alpha_j$ from $u$ to get a shorter word $u'$ that still takes us from $s_k$ to $s_{k+1}$; it just cuts out the unnecessary loop from $t_i$ back to $t_j=t_i$. By cutting out all such loops, we can ensure that the states $t_1,\dots,t_m$ are all distinct.

Now it may be that the only path from $s_k$ to $t$ leads through all of the states $s_1,\dots,s_{k-1}$ that we’ve already visited. In that case the states $t_1,\dots,t_{k-1}$ are a permutation of the states $s_1,\dots,s_{k-1}$. But even if that’s the case, $t_k$ will be different from the states $t_1,\dots,t_{k-1}$ and therefore different from all of the states in $A$. It will be a state through which the word $w_k$ didn’t take us. If we now set $w_{k+1}=w_k\alpha_1\alpha_2\dots\alpha_k$, we’ll have a word of length at most $\frac12k(k-1)+k=\frac12k(k+1)$ that takes us through the $k+1$ states $s_1\dots,s_k,t_k$. Letting $s_{k+1}=t_k$, we have a word $w_{k+1}$ of length at most $\frac12k(k+1)$ that takes us through the $k+1$ states $s_1,\dots,s_{k+1}$.

By induction, then, there must be a word $w_n$ of length at most $\frac12n(n-1)$ that takes us through $n$ distinct states $s_1,\dots,s_n$ and therefore through every state of the machine.