0
$\begingroup$

Let $M$ be a DFA.

I would like to prove that $L(M)$ is infinite if and only if there exists a string $w \in L$ such that $|Q| \leq |w| \leq 2 \cdot |Q| $.

My idea was to use the fact that the shortest string in $L(M)$ is of size at most $|Q|$, but I am not sure precisely how I should use this. Or is there a different approach?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ if the string length |w| > |Q| that means that there is a loop , before getting accepted , so you can generate as many strings from that loop, making it a infinite language $\endgroup$ – Pavan Kumar Munnam Dec 9 '16 at 12:47
  • $\begingroup$ I see. But for the othe direction, I do not know that M is a minimal automaton, so can I really say that for every such M I can find |Q|<|w|<2*|Q|? Because one can increase Q as much as he wants, and while there is inf number of strings, perhaps not for each Q there is a word with size between |Q| and2|Q|? $\endgroup$ – Eric_ Dec 9 '16 at 13:35
  • $\begingroup$ even though M is not a minimal machine it should have finite states, that is the definition of regular language right, so if you find one string which is greater than Q its enough to show it is infinite $\endgroup$ – Pavan Kumar Munnam Dec 9 '16 at 14:09
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 10 '16 at 14:34
5
$\begingroup$

The proof makes use of the pigeonhole principle.

First suppose $L(M)$ is infinite. This means that for every $k \geq 0$ there exists a $w \in L(M)$ with $|w| \geq k$. Therefore there must in particular exist a $w$ with $|w| \geq |Q|$. Take the shortest such $w$ and let $w = a_1 a_2 \ldots a_k$. When reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence: Now consider the first such repeated pair, $q_i$ and $q_j$. We have that the substring $a_i...a_j$ has length at most $|Q|$. The string $a_1 \ldots a_i \ldots a_j a_i \ldots a_j \ldots a_k$ will be accepted, and its length is at most $2|Q|$.

Next suppose there is a string $w \in L(M)$ where $|Q| \leq |w| \leq 2 |Q|$. Again consider the states that $M$ will visit when reading $w$ and let $w = a_1 a_2 \ldots a_k$. As in the proof of the converse implication above, we notice that when reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence. Again, consider the first such repeated pair, $q_i$ and $q_j$. We have that for every $m \geq 0$ that the string $a_1 \ldots (a_i \ldots a_j)^m a_{j+1} \ldots a_k$ will be accepted, and this proves that $L(M)$ is infinite.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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