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$.
finite state machine is strongly connected
-
0@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? – 2012-10-02
1 Answers
HINTS:
$\displaystyle\frac{n(n-1)}2=\sum_{k=1}^{n-1}k$.
Let $A$ be a set of $k$ states, where $k
, 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
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
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.
-
0@Brian sure Brian – 2012-10-13