The Pumping Lemma is useful for disproving the regularity of a language. It states that for strings beyond a certain length in your infinite-sized regular language, you are bound to find repeating strings in the form xy^i z, where xyz is in your language already.
It’s useful, because if the pumping lemma applies to a language, you know that it’s regular. If the pumping lemma does not apply to an infinite language, you only know that the pumping lemma does not apply to that language.
June 7, 2008 at 3:29 pm
The Pumping Lemma is useful for disproving the regularity of a language. It states that for strings beyond a certain length in your infinite-sized regular language, you are bound to find repeating strings in the form xy^i z, where xyz is in your language already.
It’s useful, because if the pumping lemma applies to a language, you know that it’s regular. If the pumping lemma does not apply to an infinite language, you only know that the pumping lemma does not apply to that language.