# What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?

What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite?

I checked this post How to determine if an automata (DFA) accepts an infinite or finite language? and in the answer provided by Rick Decker, he states, "The language accepted by a DFA M with n states is infinite if and only if M accepts a string of length k, where n≤k<2n." But, if I have a string of minimum length 'n-1' that gets accepted by a DFA having 'n' states, it proves that the language accepted by the DFA is infinite. So, is the minimum lower bound 'n' or 'n-1'?

Possibly the off-by-one is due to the fact that sometimes we (slightly) abuse the definition of DFAs by using a transition function that is not total. Of course, such a DFA is equivalent to a DFA with a total transition function and one more state, so the distinction usually does not matter. However, since you are after an exact bound on the length of a string as a function of the numbers states, we have to be careful.

To avoid confusion let's consider total transition functions only.

Claim: Let $$D$$ be a DFA with $$n$$ states. $$L(D)$$ is infinite if and only if $$D$$ accepts some string $$x$$ with $$|x| \ge n-1$$.

Proof: Let $$\Sigma$$ and $$\delta$$ be the alphabet and the transition function of $$D$$, respectively.

One direction is trivial: if $$L(D)$$ is infinite, then $$L' = L(D) \setminus \left( \cup_{i=0}^{n-2} \Sigma^i \right)$$ is also infinite (since $$\cup_{i=0}^{n-2} \Sigma^i$$ is finite) and we can pick any $$x \in L'$$.

Suppose then that $$D$$ accepts some $$x$$ with $$|x| \ge n-1$$. There must be some (not necessarily simple) path $$\pi_x$$ from the initial state $$q_0$$ of to an accepting state $$q_A$$ of $$D$$. Our goal is to show that there are infinitely many such paths. In particular, it suffices to show that there is a path $$\pi^*$$ from $$q_0$$ to $$q_A$$ that is not simple (i.e., it has some repeated vertex), since then $$\pi^*$$ must contain a cycle.

If there is some $$s \in \Sigma$$ such that $$\delta(q_A,s)$$ can reach $$q_A$$ (possibly $$\delta(q_A,s)=q_A)$$ via some path $$\pi'$$, we can choose $$\pi^* = \pi_x \circ \pi'$$, where $$\circ$$ denotes concatenation. Otherwise, there is at least one state $$q$$ that cannot reach $$q_A$$, which means that $$\pi_x$$ does not traverse $$q$$. Since the length of $$\pi_x$$ is at least $$n-1$$, and at most $$n-1$$ vertices can be traversed, the pigeonhole principle ensures that $$\pi_x$$ cannot be simple (i.e., we can choose $$\pi^* = \pi_x$$). $$\square$$

The above bound is tight in the sense that, for every $$n \ge 1$$, you can build a DFA $$D$$ with $$n$$ states such that all strings of length at most $$n-2$$ are accepted but $$L(D)$$ is finite (the graph of the DFA is a directed path with vertices $$q_0, \dots, q_{n-1}$$ where $$q_0, \dots, q_{n-2}$$ are accepting, and $$q_{n-1}$$ is a catch-all rejecting trap).

Moreover, the following holds:

Claim: if $$L(D)$$ is infinite then there must be some string $$x$$ with $$n-1 \le |x| \le 2n-2$$ that is accepted by $$D$$.

Proof: Let $$\pi$$ be the shortest accepting (non-simple) path of length at least $$2n-1$$. Since $$\pi$$ traverses $$2n > n$$ states (counting repetitions), $$\pi$$ must include a cycle. Deleting the cycle from $$C$$ yields an accepting path of length at most $$2n-2$$ and at least $$2n-1-n=n-1$$. $$\square$$

This is tight in the sense that there are DFAs $$D$$ such that $$L(D)$$ is infinite but all strings $$x$$ with $$n-1 \le |x| \le 2n-3$$ are rejected (the graph of the DFA is a directed cycle with states $$q_0, \dots, q_{n-1}$$, only state $$q_{n-2}$$ is accepting).

To summarize

If $$D$$ be a DFA with $$n$$ states then $$L(D)$$ is infinite if and only if $$D$$ accepts some string $$x$$ with $$n-1 \le |x| \le 2n-2$$.

• hey, thanks Steven for clarifying, and explaining it rigorously! Oct 23, 2023 at 14:49