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
    What have you tried? This is pretty straightforward once you are clear about what exactly this is saying.2012-10-02
  • 0
    Think about what the hypothesis tells you and what is the connection between that and what you want to prove.2012-10-02
  • 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 knot 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

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
    I didn't get the second hint. can you please explain?2012-10-02
  • 0
    @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.2012-10-02
  • 0
    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.2012-10-02
  • 0
    @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.2012-10-02
  • 0
    @Brian. I didn't get it still. Why is it that we are considering states that are not in A.2012-10-13
  • 0
    @Brian. Why is it There is a word of length at most k takes the machine from s to a state not in A.2012-10-13
  • 0
    @user34790: Because you want a word that takes the machine to every state. At each stage $A$ is the set of states that you’ve already hit, and you need to show that you can hit one of the remaining states without using up too much input. There’s a word of length at most $k$ that takes $M$ from $s$ to a state not in $A$ because (1) we can choose a word that hits a new state with each letter, and (2) there are only $k-1$ states in $A$ besides $s$. Even if our first $k-1$ moves take us to these states in $A$, the $k$-th move will hit something new.2012-10-13
  • 0
    @Brian. I didn't get it why it is that the kth move will hit something new. Lets say I have k-1 states beside the initial state. It is possible that I could be looping among the k-1 states for input of length k or more than k2012-10-13
  • 0
    @user31820: But you can always choose your input so that you **don’t** keep looping. Remember, $M$ is strongly connected. You can definitely get from $s$ to some $t\notin A$, and any segment of input that takes you from one state back to that state can be deleted: you didn’t need it.2012-10-13
  • 0
    @Brian I didn't get what is A. A is the set of given k states right. Ok so I will assume that each input will take me to a new state and I will visit every state with a string of length k-1. This makes it that the length of string for visiting each state will be k-1 not n(n-1)/2.2012-10-13
  • 0
    @user31820: Suppose that you visit the states in the order $s_1,\dots,s_n$. In the worst case it takes one input to get from $s_1$ to $s_2$, $2$ more inputs to get to $s_3$, $3$ more inputs to get to $s_4$, and so on, for a total of $$1+2+3+\ldots+(n-1)=\frac{n(n-1)}2\;.$$2012-10-13
  • 0
    @Brian. Yeah this way I understood. But the thing with getting to a state not in A. I didn't get it. We are given that there are k states in A. So what is meant by going to a state not in A. This is what I didn't understand. I could understand your last example. But I want to make sure that I understand every part.2012-10-13
  • 0
    @Brian can we discuss in chat. Just a few minutes and I will be clear I am sure2012-10-13
  • 0
    @user31820: I think that it would be more effective at this point for me to expand my answer to a complete solution. Give me a few minutes to do that, and then see whether that straightens things out.2012-10-13
  • 0
    @Brian sure Brian2012-10-13