Problem Detail: Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $sigma in L$, with $lvert sigma rvert ge N$ there exist strings $alpha$, $beta$ and $gamma$ such that $lvert alpha beta rvert le N$ and $lvert beta rvert ne epsilon$, and for all $k$ it is $alpha beta^k gamma in L$. It is widely stated that the converse isn’t true, but I haven’t seen any clear example. Any suggestions? Clearly the proof that the offending language isn’t regular has to use stronger methods than the typical “doesn’t satisfy the pumping lemma”. I’d be interested in simple examples, to present in introductory formal languages classes.
Asked By : vonbrand
Answered By : Hendrik Jan
The language ${ $ a^nb^n mid n ge 1 } cup { $^kw mid kneq 1, win {a,b}^* }$ seems to be simple. The second part is regular (and can be pumped). The first part is nonregular, but can be pumped “into” the second part by choosing $$$ to pump. (added) Of course, this can be generalized to $$L cup { $^k mid kneq 1 } cdot {a,b}^*$ for any $Lsubseteq {a,b}^*$. Sometimes the formulation is in the “if … then …” style: if $w$ starts with a single $$$ then it is of the form. That I personally find less intuitive. As noted by @vonbrand the (possibly) non-regular part of the language is isolated by intersecting with $${a,b}^*$. This can be separately tested using the pumping lemma if needed.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9181
