# Infinite regular language

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!

• 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 – Pavan Kumar Munnam Dec 9 '16 at 12:47
• 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|? – Eric_ Dec 9 '16 at 13:35
• 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 – Pavan Kumar Munnam Dec 9 '16 at 14:09
• 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! – Raphael Dec 10 '16 at 14:34

## 1 Answer

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.