Problem Detail: I have that language $S={a^n b^m c^mmid 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^nmid ngeq0}$ and $L_2 ={b^m c^mmid m geq0}$ prove that $L_2$ isnt regular so $L_1 L_2 = S$ is not regular too?
Asked By : user2936672
Answered By : David Richerby
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^nmid ngeq 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63793
