I have that language $S=\{a^n b^m c^m\mid n,m \geq 0\}$. How can I prove with the pumping lemma that it isn't regular? Can I use the concatenation closure and say that it's the language $L_1 = \{a^n\mid n\geq0\}$ and $L_2 =\{b^m c^m\mid m \geq0\}$ prove that $L_2$ isnt regular so $L_1 L_2 = S$ is not regular too?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ This is so close to the canonical $a^nb^n$ example that one wonders why you don't just adapt the proof for that one. Plus, our reference question contains many approaches. Community votes, please: duplicate? $\endgroup$– RaphaelCommented Sep 23, 2016 at 12:46
-
1$\begingroup$ @Raphael I think the question about concatenation is enough to make this a non-dupe. (Thanks for linking to the reference question, though: I forgot to do that in my answer.) $\endgroup$– David RicherbyCommented Sep 23, 2016 at 12:55
-
$\begingroup$ If you know how to show that $L_2$ is non regular then the same idea works for $S$ as well... $\endgroup$– BakuriuCommented Sep 23, 2016 at 15:16
-
$\begingroup$ +1, but note that even if your concatenation approach did work, that wouldn't really satisfy the "prove with the pumping lemma" requirement. $\endgroup$– ruakhCommented Sep 23, 2016 at 17:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not guaranteed to be non-regular. For example, take $L_1=\Sigma^*$, $L_2=\{a^nb^n\mid n\geq 0\}$. $L_2$ is not regular but $L_1L_2=\Sigma^*$ is regular.
To prove that $S$ is non-regular using the pumping lemma, pump a string that contains more $b$s than $c$s.
answered Sep 23, 2016 at 12:15
-
$\begingroup$ For clarity, shouldn't you say pump a string consisting of only $b$s and $c$s? Then pumping up will give a string with more $b$s than $c$s. $\endgroup$ Commented Sep 23, 2016 at 13:12
$\begingroup$
$\endgroup$
2
Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.
However ... If you want to have a result about closure of non-regular languages you can consider this one.
Theorem. If $L_1$ and $L_2$ are nonempty languages over disjoint alphabets, then their concatenation $L_1L_2$ is nonregular iff at least one of $L_1$ or $L_2$ is nonregular.
Of course, if either language is empty, then the concatenation will be empty, hence regular.
answered Sep 23, 2016 at 13:00
-
$\begingroup$ To prove the theorem, consider a FSM recognizing L1L2 and remove from it the transition states corresponding to one of L1 or L2? $\endgroup$ Commented Sep 23, 2016 at 16:51
-
$\begingroup$ @JanDvorak Exactly. When replacing in the automaton for the concatenation all transitions from one alphabet by $\epsilon$ transitions one obtains a finite state automaton for the other half. If needed these $\epsilon$ can be removed by standard techniques. (Just removing the transitions leaves us with the task of deciding where to begin/end.) $\endgroup$ Commented Sep 23, 2016 at 18:01