Pumping Theorem for Regular Languages
Learn about the 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 , where 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 of length for acceptance. The question is: when can we stop and give an answer? Since no cycle can contain more than states, we only have to test strings of the following lengths: .
If a language accepts a string of length , we can ignore one of its cycles, which is no longer than length , meaning that a string whose length is in the range 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 with lengths in the range 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, , accepts a string, , where , and where is the number of states in its associated minimal DFA. We know from the pigeonhole principle that by the time we have read the -th symbol of , a cycle has been found in an accepting path. Let’s call the substring representing the first cycle found (traversing the cycle once), and the substring leading from the initial state to the first state of the cycle (which could be empty). Then we can represent as the concatenation of three strings, , where and are just as described, and represents whatever is left in the string after all the way to where the string ends in an accepting state. The string may contain other traversals of ’s cycle and any other edges and cycles that may occur in the string after . Like , may also be empty.
Get hands-on with 1200+ tech skills courses.