Show a language is infinite

Question

Given a DFA M with n states defined over an alphabet ∑, and a string x∈L(M) such that |x|>n, I must show that the L(M) is an infinite language.

Is there any way I can prove this using the pumping lemma?

Answer 1

I'm not immediately sure why the pumping lemma needs to be involved directly. The proof idea is the same one behind the proof of the pumping lemma, and we can explain the relationship. Possibly, with that explanation in hand, you can figure out a way to work out a proof that relies on the pumping lemma directly. I think that should in theory be possible to do without too much mental gymnastics.

Imagine a DFA with three states that accepts a string of length four. This is a concrete instance of the general claim you've been asked to prove. If we can understand why this is specifically true here, it will be easier to generalize to DFAs with an arbitrary number of states.

A DFA executes one transition for every symbol of input. Each transition takes the DFA to some state. Since the string of length four is accepted, we execute four transitions - beginning with the initial state - and we end up in some accepting state. Since each transition takes the DFA to some state, we move into states four times. Since there are only three states in the DFA, that means one of the states was transitioned into more than once: we cannot transition four times around three states without visiting some state more than once. The general principle here is referred to as the Pigeonhole principle: if there are n pigeons in m holes, and n > m, then some hole has more than one pigeon. This is the same reasoning behind why the pumping lemma works, by the way.

Now, consider what this observation means. We accepted a string and, while accepting that string, some state was visited twice. This means that there is a loop in our DFA somewhere - a way to get to an earlier state from a later state - and, furthermore, it is possible to accept strings after taking the loop. If the loop can be taken once:

• it might not have been taken at all, so there is definitely a shorter string accepted by the DFA.
• it might be taken twice, so there is definitely a longer string accepted by the DFA.
• indeed, it might be taken over and over again an arbitrary number of times, so infinitely many longer strings must be in the language.

When using the pumping lemma, you typically assume a language is regular and conclude that what the pumping lemma says about regular languages - what we have said above - is true. Then, you provide a counterexample - a string of length greater than the pumping length p (more on what p is in a moment) - and conclude the assumption is false, that is, that the language is not regular.

The pumping length is essentially the number of states in some DFA for the language. If the language is regular, there are infinitely many DFAs that accept it. For the purposes of using the pumping lemma, it doesn't really matter which DFA for the language you use, since any DFA will visit some state more than once if it processes an input whose length exceeds the number of states in the DFA. Perhaps it is typical to imagine a minimal DFA for the language, which is guaranteed to exist and be unique up to isomorphism.