# finite state machine is strongly connected

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$.

-
What have you tried? This is pretty straightforward once you are clear about what exactly this is saying. – Mariano Suárez-Alvarez Oct 2 '12 at 2:57
Think about what the hypothesis tells you and what is the connection between that and what you want to prove. – Mariano Suárez-Alvarez Oct 2 '12 at 2:59
@MarianoSuárez-Alvarez The hypothesis says that you can get from any state to any other state in M since it's strongly connected. right? this is what you meant? – Mike Oct 2 '12 at 19:47

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.

-
I didn't get the second hint. can you please explain? – Mike Oct 2 '12 at 17:42
@Mike: There are only $k-1$ states in $A$ besides $s$. There are states not in $A$, and they’re all accessible from $s$. Even if the only way to get to any of them involves hitting every state in $A$ again, that’s still only $k-1$ steps. – Brian M. Scott Oct 2 '12 at 19:45
OK, I udnerstand that. But how you proof it. Is it done by induction? since we are trying to prove for any w and n. – Mike Oct 2 '12 at 19:49
@Mike: No, you just have to show that there is at least one $w$ of length $\le n(n-1)/2$ that hits every state. You’re at one state to begin with. One input character takes you to a second. By (2) above it takes at most $2$ more input characters to reach a third, $3$ more after that to reach a fourth, and so on. Then use (1) above. – Brian M. Scott Oct 2 '12 at 19:56
@Brian. I didn't get it still. Why is it that we are considering states that are not in A. – user34790 Oct 13 '12 at 22:29