2
$\begingroup$

Why is it that the test for an infinite language on the DFA $M$ has an upper bound of $2n$?

That is to say, when testing for a string of length $k$, why does the theorem say:

$$n \leq k < 2n$$

I understand the lower bound of $n$ IAW the Pumping Lemma of $|w| \geq n$. I'm just not sure why $2n$ was chosen and I think I'm over complicating it.

$\endgroup$
  • $\begingroup$ What does IAW stand for? $\endgroup$ – Yuval Filmus Feb 18 '18 at 6:51
  • $\begingroup$ Do you know the proof of this statement? $\endgroup$ – Yuval Filmus Feb 18 '18 at 6:51
  • $\begingroup$ @YuvalFilmus In Accordance With $\endgroup$ – pstatix Feb 18 '18 at 16:29
  • $\begingroup$ @YuvalFilmus I do not because my text (by John Hopcroft) does not have this theorem outlined (although I believe it should be) $\endgroup$ – pstatix Feb 18 '18 at 16:30
1
$\begingroup$

The upper bound comes also from the proof of the pumping lemma. If you have a DFA with $n$ states, you know that if it accepts a word in length $\ge n$ then the word passes through a circle in the states, thus you can repeat the circle as many times as you like and get an infinite language.

Now, for the upper bound, assume the DFA is infinite, and accepts a word of length $\ge2n$. Now, when you run the word on the DFA, and since the DFA has only $n$ states, there must be a cycle. That cycle must be of length $\le n$. You can now remove a number iterations from that circle such that you will get a word $w$ of length $n\le |w| < 2n$.

The proof is even easier when you use the pumping length $n$ derived from the pumping lemma. Just show that for a word $w=xyz$ where $|w|\ge 2n$, since $|xy|\le n$ and $|y|>0$ there exists an $i\in \mathbb{N}$ such that $n\le |xy^iz| < 2n$.

$\endgroup$
0
$\begingroup$

Let me start with a statement and proof of the theorem.

Theorem I. Suppose that $L$ is a regular language accepted by a DFA with $n$ states. Then $L$ is infinite if and only if $L$ contains a word whose length is between $n$ and $2n-1$.

Proof. Let the DFA have states $Q$, accepting states $F$, transition function $\delta$, and initial state $q_0$.

Suppose first that $L$ is an infinite regular language. Since $L$ is infinite, it contains a word whose length is at least $n$. Let $w = w_1 \ldots w_N$ be such a word of minimum length. Let $\alpha_i$ denote the state of the DFA after reading the first $i$ letters of $w$. Since the DFA only has $n$ states, the sequence $\alpha_0,\ldots,\alpha_n$ must have duplicates, say $\alpha_i = \alpha_j$, where $i < j$. As in the proof of the pumping lemma, this implies that the word $z = w_1 \ldots w_i w_{j+1} \ldots w_N$ also belongs to $L$. By the definition of $w$, we must have $|z| < n$. Since $|w| = |z| + j-i$ and $j-i \leq n$, it follows that $|w| < 2n$. By definition, $|w| \geq n$, and so $w \in L$ is a word whose length is between $n$ and $2n-1$.

The other direction follows directly from the pumping lemma. $\quad\square$

Note that in order for $L$ to be infinite, it suffices that it contains a word of length at least $n$. That is, for this direction we don't need the additional condition that the word has length less than $2n$. This shows that the following theorem also holds:

Theorem II. Suppose that $L$ is a regular language accepted by a DFA with $n$ states. Then $L$ is infinite if and only if $L$ contains a word whose length is at least $n$.

Indeed, the proof of Theorem II is much easier, since any infinite language contains a word of length at least $n$, for any $n$. However, Theorem I is stronger, since the criterion it suggests can be checked algorithmically, since there are only finitely many words whose length is between $n$ and $2n-1$ (though there are much more efficient ways to determine whether the language accepted by a DFA is infinite).

We can combine both theorems to obtain a theorem superseding both (that is, stronger than both):

Theorem III. Suppose that $L$ is a regular language accepted by a DFA with $n$ states.

  1. If $L$ is infinite then it contains a word whose length is between $n$ and $2n-1$.
  2. If $L$ contains a word whose length is at least $n$, then it is infinite.

However, this is not a characterization, that is, it doesn't state an "if and only if" criterion for infinitude.


Let us now consider the question of optimality of Theorem III. You mentioned that you are happy with the lower bound of $n$, but in fact this lower bound can be improved, depending on the exact definition of DFA. If you allow the transition function $\delta$ to be partial, then the lower bound is indeed tight:

Lemma 1. For every $n \geq 1$ there exists a DFA over $\Sigma = \{a\}$ with $n$ states whose language is finite but contains words of all lengths smaller than $n$.

Proof. Let $Q = F = \{q_0,\ldots,q_{n-1}\}$, and define $\delta(q_i,a) = q_{i+1}$ for $i < n$ (we leave $\delta(q_n,a)$ undefined). Then $L = \{\epsilon,a,\ldots,a^{n-1}\}$. $\quad\square$

If you insist that $\delta$ be total (we call such a DFA total), you can improve the lower bound:

Lemma 2. Suppose that $L$ is a regular language accepted by a total DFA with $n$ states. If $L$ contains a word of length at least $n-1$ then $L$ is infinite.

Proof. If $L$ contains a word of length at least $n$ then this follows from Theorem II, so suppose that $w = w_1 \ldots w_{n-1}$ has length $n-1$. Let $\alpha_i = \delta(q_0, w_1 \ldots w_i)$. If $\alpha_0,\ldots,\alpha_{n-1}$ contains duplicates then $w$ can be pumped as in the proof of the pumping lemma, so $L$ is infinite. Otherwise, $\{\alpha_0,\ldots,\alpha_{n-1}\} = Q$. Let now $\sigma \in \Sigma$ be an arbitrary symbol. Then $\delta(\alpha_{n-1},\sigma) = \alpha_i$ for some $0 \leq i \leq n-1$. It follows that $w(\sigma w_{i+1} \ldots w_{n-1})^t \in L$ for all $t \geq 1$ (possibly $w_{i+1} \ldots w_{n-1} = \epsilon$), and so $L$ is infinite. $\quad\square$

Lemma 3. For every $n \geq 1$ there exists a total DFA over $\Sigma = \{a\}$ with $n$ states whose language is finite but contains words of all lengths smaller than $n-1$.

Proof. Let $Q = \{q_0,\ldots,q_{n-1}\}$, $F = \{q_0,\ldots,q_{n-2}\}$, and define $\delta(q_i,a) = q_{i+1}$ for $i < n$ and $\delta(q_{n-1},a) = q_{n-1}$. Then $L = \{\epsilon,a,\ldots,a^{n-2}\}$. $\quad\square$

Lemma 2 shows that Theorems I–III can be improved for total DFAs, an improvement which we leave to the reader. Let us now turn our attention to the upper bound.

Lemma 4. For every $n \geq 1$ and $m \in \{n,\ldots,2n-1\}$ there exists a total DFA with $n$ states whose language is infinite, contains a word of length $m$, and doesn't contain a word of any length in $\{n,\ldots,2n-1\} \setminus \{m\}$.

Proof. Let $Q = \{q_0,\ldots,q_{n-1}\}$, $F = \{q_{m-n}\}$, and define $\delta(q_i,a) = q_{i+1}$ for $i < n$ and $\delta(q_{n-1},a) = q_0$. Then $L = \{a^{m-n}, a^m, a^{m+n}, \ldots\}$. $\quad\square$

This shows, in particular, that $2n-1$ cannot be replaced by a smaller number.


What more can be said?

Definition. A set $S \subseteq \mathbb{N}$ is $n$-total if every infinite language accepted by a DFA having $n$ states contains a word whose length is in $S$. A set $S$ is minimally $n$-total if it is $n$-total and all of its proper subsets are not $n$-total.

As an example, $\{n,\ldots\}$ is $n$-total and $\{n,\ldots,2n-1\}$ is minimally $n$-total.

Open problem. Characterize all minimally $n$-total sets.

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