Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
there is a subtlety that its true only for RLs with infinite words. wikipedia has an example. –  vzn Jan 27 '13 at 1:16
    
In my definition, a word (string) is finite. –  vonbrand Jan 27 '13 at 2:05

1 Answer 1

up vote 6 down vote accepted

The language $\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{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 k\neq 1 \} \cdot \{a,b\}^*$ for any $L\subseteq \{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.

share|improve this answer
    
Thanks! That certainly fits the bill. I'm still interested in more examples. –  vonbrand Jan 27 '13 at 2:07
    
Oh, and for completeness: To prove it isn't regular, intersect with $\$ a^* b^*$ and erase $\$$ with a homomorphism. –  vonbrand Jan 27 '13 at 2:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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