Trisha Shetty (Editor)

Pumping lemma

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In the theory of formal languages, the pumping lemma may refer to:

  • Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular
  • Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free
  • Pumping lemma for indexed languages
  • Pumping lemma for regular tree languages
  • References

    Pumping lemma Wikipedia


    Similar Topics