To show that INFINITEDFA is decidable, meaning to construct a TM $M$ that decides INFINITEDFA.
This means that for all DFA's A we want
• If L(A) is an infinite language then M(<A>) accepts
• If L(A) is a finite language then M(<A>) rejects.
To construct a TM M we use the following claim.
Claim: Suppose A is a DFA with p states and alphabet Σ.
Let BA = { w ∈ Σ* : w ∈ L(A) and p ≤ |w| ≤ 2p } .
Then L(A) is infinite if and only if BA != ∅.
This means that to test whether or not L(A) is infinite, we need only test whether or not BA is empty. The latter can be done using the machine Mdfa since BA is a finite set.
So, just run Mdfa on the strings w ∈ L(A) such that p ≤ |w| ≤ 2p.
If Mdfa accepts at least one string w then the DFA $A$ is accepted by M otherwise rejected.
Hence INFINITEDFA is Turing decidable (recursive) .
Now, I prove the claim.
In the first part of the proof, we assume that BA != ∅.
We want to show that L(A) is infinite. Note that the number of states p in the DFA is the p of the Pumping Lemma applied to the regular language L(A).
Since BA is non-empty, there is some string s ∈ BA. By definition of BA we have s ∈ L(A) and |s| ≥ p, so there exist x, y, z such that s = xyz where y is non empty and |xy| <= p.
So, we get that xyi z ∈ L(A) for all i ≥ 0. This means that L(A) is infinite.
In the second part of the proof, we assume that L(A) is infinite.
We want to show that BA != ∅. Let s be a shortest string in L(A) such that |s| ≥ p. (Such an s exists since L(A) is infinite.)
If |s| ≤ 2p then s ∈ BA so we have shown BA != ∅.
Now, suppose towards a contradiction that |s| > 2p. Apply the Pumping Lemma to the regular language L(A) to write s = xyz such that the three conditions of the Pumping Lemma hold.
Setting i = 0 in the first condition tells us that xz ∈ L(A).
Again we have |y| ≤ p.
So |xz| = |s| − |y| > 2p − p = p, meaning xz is a string in L(A) with length strictly greater than p, but is shorter than s.
This contradicts the assumption that s was the shortest such string.