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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ there is a subtlety that its true only for RLs with infinite words. wikipedia has an example. $\endgroup$– vznCommented Jan 27, 2013 at 1:16
-
$\begingroup$ In my definition, a word (string) is finite. $\endgroup$– vonbrandCommented Jan 27, 2013 at 2:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Jan 27, 2013 at 0:47
-
$\begingroup$ Thanks! That certainly fits the bill. I'm still interested in more examples. $\endgroup$– vonbrandCommented Jan 27, 2013 at 2:07
-
$\begingroup$ Oh, and for completeness: To prove it isn't regular, intersect with $\$ a^* b^*$ and erase $\$$ with a homomorphism. $\endgroup$– vonbrandCommented Jan 27, 2013 at 2:09
-
-
$\begingroup$ I am afraid this construction is in fact incorrect. It is important to notice that the pumping lemma allows extraction by allowing $k=0$. Take $\$a^nb^n$, you said it can be "pumped into the second part by choosing $\$$ to pump", but $\$$ cannot be extracted because $a^nb^n$ clearly does not belong to the language you specified. And it cannot be patched in a simple way: $a^nb^n$ cannot be pumped, so it cannot be added into the language. However, I did manage to find a correct (I believe) construction on Wikipedia (at the time of writing this comment), though it is far more complex. $\endgroup$ Commented Mar 11, 2022 at 10:06
-
$\begingroup$ @RuifengXie The second part of the language can also start with zero symbols $\$$. $\endgroup$ Commented Mar 11, 2022 at 20:08