2
$\begingroup$

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'?

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ hey, thanks Steven for clarifying, and explaining it rigorously! $\endgroup$ Commented Oct 23, 2023 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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