Decider for DFA_FIVENESS

1. Decide if the language is infinite.
2. If the language is finite, describe a method for counting the total number of strings that is guaranteed to always halt.

First I'll explain what's NOT A SOLUTION:

Define the TM BAD as follows

BAD =

"On input < A > where A is a DFA

1. Decode the string < A > and prepare to simulate A on one of the TM tapes
2. For each string x in Σ*
3. Simulate A running on x
4. If A accepts, increment a counter on one of the TM tapes
5. Else, don't increment the counter
6. Goto 2 with next string (end of the current loop iteration)
7. If the counter reads 5 at the end of the computation, ACCEPT
8. Else, REJECT"

This is BAD because:

The TM goes into an infinite loop regardless of A. Technically, L(BAD) = {} = the empty language and not the language of interest!!!! This is because we iterate through the set of all strings- an infinite set- and have no stopping condition. Even if this always halted for "YES" answers as is definitely required for a valid TM, we don't want any infinite loops on "NO" answers either, as we want a DECIDER. So a modification that knows when to stop for some languages of size 5, but goes into infinite loops on empty languages (for example) would be bad as no infinite loops at all should occur.

So how do we fix it? We have to provide and ending condition. and argue why we don't have to keep on trying to accept more states ad - infinitum -past that ending condition.

Let's see the fix and then argue why the fix works:

GOOD =

"On input < A > where A is a DFA

1. Decode the string < A > and and prepare to simulate A on one of the TM tapes
2. Count the number of states and store this number as the variable p on one of the tapes
3. For each string x in Σ^{[p, 2p-1]} (the notation signifies all strings of length &ge p but < 2p)
4. Simulate A running on x
5. If A accepts, "REJECT" (|L(A)| = ∞ )
6. Else, Goto 3 with next string or Goto 7 if read final string in range (end of the current loop iteration)
7. For each string x in Σ^{[0, p-1]}
8. Simulate A running on x
9. If A accepts, increment a counter on one of the TM tapes
10. Else, don't increment the counter
11. Goto 7 with next string (end of the current loop iteration)
12. If the counter reads 5 at the end of the computation, ACCEPT
13. Else, REJECT

So why does this work?

Lines 3-6 are using the pumping lemma to determine whether the language is infinite. How? If the language is infinite, there are strings of arbitrary length, including length ≥ to the number of states (p). We claim that some string of length in the range [p, 2p-1] must be accepted. Why? Suppose not. Let l be the shortest length of any accepted string of length ≥ p. Suppose l is not in the desired range, so l ≥ 2p. Let x be an accepted string of length l. Since l > p we can pump x down and obtain a string y in the language of length shorter than l. Furthermore, pumping down implies extracting a string of length at most p so the length of y is ≥ l-p ≥ 2p - p = p. In other words, we contradicted the definition of x being the shortest string longer than p so our assumption was wrong and we must have a string of length in the range [p, 2p-1]. This shows that if the language is infinite, we shall detect this fact by catching a string in the appropriate length range. Conversely, if the language is not infinite, there won't be any strings of length range [p, 2p-1] since we would be able to pump-up such strings ad-infinitum. This shows that we REJECT in line 56 exactly when the language is infinite.

Lines 7-13 can only be reached if the language is finite. Furthermore, the pumping lemma guarantees no strings of length ≥ p (as would pump up ad-infinitum) and so all the strings are of length at most p-1. Thus iterating through all such strings and counting how many are accepted guarantees that the counter variable will hold the correct number accepted strings at the end of the comptation. Thus, lines 12-13 guarantee accepting exactly when there are 5 strings in L(A).

How about CFG-FIVENESS?

Q: What part of the argument still works?

Q: What part of the argument fails?