Pumping Theorem for Regular Languages

Infinite regular languages

We know that a decision algorithm can be developed to detect whether a DFA’s language is infinite. If a DFA accepts a string of length greater than or equal to $p$, where $p$ is the number of states in the DFA, we know there is a cycle in an accepting path, so the language is infinite. Therefore, we could test all strings in $\Sigma^*$ of length $p,p+1,p+2...$ for acceptance. The question is: when can we stop and give an answer? Since no cycle can contain more than $p$ states, we only have to test strings of the following $p$ lengths: $p,p+1,p+2,...,2p-2,2p-1$.

If a language accepts a string of length $2p$, we can ignore one of its cycles, which is no longer than length $p$, meaning that a string whose length is in the range $[p,2p-1]$ must also be accepted.

Remember: To determine by computer whether the language of a finite automaton is infinite, it is sufficient to test all strings in $\Sigma^+$ with lengths in the range $[p,2p-1]$ for acceptance.

As stated earlier, we could also convert the language’s automaton to a regular expression. If a Kleene star is present, then the language is infinite.

Note: To determine whether the language of a finite automaton is infinite, convert the automaton to a regular expression and look for a Kleene star.

Ideas behind the pumping theorem for infinite regular languages

Suppose a regular language, $L$, accepts a string, $s$, where $|s| \geq p$ ...