patternModerate
Regular language with pumping lemma
Viewed 0 times
withregularlanguagepumpinglemma
Problem
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?
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?
Solution
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.
To prove that $S$ is non-regular using the pumping lemma, pump a string that contains more $b$s than $c$s.
Context
StackExchange Computer Science Q#63793, answer score: 10
Revisions (0)
No revisions yet.