Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.