Are there some languages not regular and/or not context-free in which the proof by contradiction fails? Why we need a "more specific" version of pumping lemma?

  • $\begingroup$ What do you mean by "a more specific version of pumping lemma"? $\endgroup$
    – justhalf
    Commented Jun 20, 2017 at 9:40
  • $\begingroup$ I mean Myhill–Nerode theorem or some other generalization. $\endgroup$
    – Jackie
    Commented Jun 20, 2017 at 9:52
  • $\begingroup$ This may help: en.wikipedia.org/wiki/… $\endgroup$
    – Welbog
    Commented Jun 20, 2017 at 13:28
  • $\begingroup$ @Welbog: I see the question as more like: "Is there any non-regular language that cannot be proven non-regular by using pumping lemma?" So not about why pumping lemma can't be used to prove that a language is regular. $\endgroup$
    – justhalf
    Commented Jun 21, 2017 at 4:18
  • $\begingroup$ Exact, I mean what @justhalf says. $\endgroup$
    – Jackie
    Commented Jun 21, 2017 at 6:39

1 Answer 1


The standard formulations of the regular pumping lemma all force the pumped part to be at a specific place -usually the beginning of the word- and of a very restricted length. Thus you can trick the lemma by contructing a language that allows just about anything in the first part of the string and gets complicated in the second part. Take for example:

$$\{wba^nb^n\mid w\in\{a,b\}^+,\ n>0\}\,.$$ Since the pumping lemma just states the existence of its constants, you can pump anything in the first part of the language without leaving it. However, due to the last component the language is not regular.

  • $\begingroup$ The word $aba^nb^n$ cannot be pumped, though. Don't forget you're allowed to pump down! $\endgroup$ Commented Jun 14, 2019 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.