# Which are the cases where the “pumping lemma” doesn't work?

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?

• What do you mean by "a more specific version of pumping lemma"? – justhalf Jun 20 '17 at 9:40
• I mean Myhill–Nerode theorem or some other generalization. – Jackie Jun 20 '17 at 9:52
• This may help: en.wikipedia.org/wiki/… – Welbog Jun 20 '17 at 13:28
• @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. – justhalf Jun 21 '17 at 4:18
• Exact, I mean what @justhalf says. – Jackie Jun 21 '17 at 6:39

$$\{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.
• The word $aba^nb^n$ cannot be pumped, though. Don't forget you're allowed to pump down! – Yuval Filmus Jun 14 '19 at 12:26