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?
$\begingroup$
$\endgroup$
5
-
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$– ShaullSep 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$– Gilles 'SO- stop being evil'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$– SubhayanSep 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$– SubhayanSep 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$– Hendrik JanSep 28, 2013 at 12:55
Add a comment
|