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?

  • 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$ – Raphael Sep 23 '16 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 Richerby Sep 23 '16 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$ – Bakuriu Sep 23 '16 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$ – ruakh Sep 23 '16 at 17:16

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.

  • $\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$ – Rick Decker Sep 23 '16 at 13:12

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.

  • $\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$ – John Dvorak Sep 23 '16 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$ – Hendrik Jan Sep 23 '16 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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