I am currently studying the pumping lemma for regular languages and I am trying to come up with an example where even if the language can be pumped it is not regular. Which condition of the lemma should be broken such that I can find a language like that?

  • 1
    $\begingroup$ What do you mean "which condition should be broken"? The idea is that all the conditions do hold, yet still the language is not regular. $\endgroup$
    – Shaull
    Sep 28, 2013 at 11:26
  • 1
    $\begingroup$ There's a counter-example in Wikipedia, but it doesn't give any intuition as to how where this example comes from. $\endgroup$ Sep 28, 2013 at 12:00
  • 1
    $\begingroup$ @Gilles nice.. i did not know of it either, so thanks :). And you should make this to an answer. $\endgroup$
    – Subhayan
    Sep 28, 2013 at 12:30
  • $\begingroup$ @user1704040 if you relax any of the conditions, the lemma won't hold, try to relax the three one by one, and see there's always some language 'fits' into it. $\endgroup$
    – Subhayan
    Sep 28, 2013 at 12:32
  • $\begingroup$ See the related Languages that satisfy the pumping lemma but aren't regular?. The remark of @Shauli was to the point here however. $\endgroup$ Sep 28, 2013 at 12:55