Regular Languages - Infiniteness Problem

Let $\mathcal{A}$ be DFA a with $n$ states.

• If there is a word $w$ with length $k \geq n$ accepted by $\mathcal{A}$ , then the language accepted by $\mathcal{A}$ is infinite. Observe, that such word $w$ has the form $w = xsy$ , where $s$ is nonempty and the word $xs^\mu y$ is accepted by $\mathcal{A}$ , for all $\mu \in \N_0$ . In other words: there exists a loop in $\mathcal{A}$ . Clearly the length of such loop, is smaller or equal $n$ .

• If there is a word $w$ witch length $k \geq 2n$ accepted by $\mathcal{A}$ , there there exists a word $w^\prime$ accepted by $\mathcal{A}$ with length $k^\prime < 2n$ . Note that the word $w$ has the form $w = xs^\mu y$ , for some $\mu \in \N_0$ , with $0 < |s| \leq n$ and such that the word $x s^\nu y$ is accepted by $\mathcal{A}$ for every $\nu \in \N_0$ (intuition: the subword $x$ is used to each the loop mentioned above, the word $s^\nu$ passes the loop, and $y$ is used to reach the accepting state). Let $w^\prime = xy$ . Since $|w| = |xs^\mu y| \leq 2n$ and $0 < |s| \leq n$ , then $|w^\prime| < 2n$ .

Using the facts above, we conclude, that if there exists a word $w$ , such that $n \leq |w| < 2n$ accepted by $\mathcal{A}$ , then $\mathcal{A}$ accepts a infinite language. In order to determine, if a given DFA with $n$ states accepts or does not accept a infinite language, we need to check all words with length between $n$ and $2n-1$ . In case if $n = 23$ , we need to investigate the words not longer than $2\cdot 23-1 = 45$ .