1
$\begingroup$

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

  • 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 1

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

  • 0
    @Brian sure Brian2012-10-13