How to prove that the language $L = \{a^nb^mc^n | m, n ≥ 0\}$ is not regular using pumping lemma?

Question

I have viewed the examples and solved problem for $\{a^nb^n\}$ but for three (a,b,c) $L = \{a^nb^mc^n | m, n ≥ 0\}$ have not found. So, how can I do it? It will help in understanding more than two means for $a,b,c$.

Answer 1

Proof by contradiction with Pumping Lemma

• Let assume to the contrary that the language $L$ is regular. Let the pumping length for the language $L$ be $p$.

• Consider $s=a^pb^mc^p \in L$, for $m \geq 0$.

• Consider all possible ways to divide $s = xyz$, where $|y|>0$, $|xy| \leq p$.

• Let $|y|=j>0$, then $y=a^j$. By pumping lemma, $xy^iz \in L$, $\forall{i} \in\{0,1,2,\ldots\}$.

• Now $xy^0z = xz = a^{p-j}b^mc^p \in L$ by pumping Lemma, but number of $a$'s = $p-j < p =$ number of $c$'s in the string, which implies $xz \not \in L$, by the definition of $L$, hence a condtradiction.

Answer 2

Main idea: The pumping lemma applies to any word longer than the pumping length. Including those where $m=0$.

Answer 3

If you already know that the language $K = \{a^nc^n \mid n \geqslant 0\}$ is not regular, there is no need to use the pumping lemma. Indeed, if $L$ were regular, then the language $L \cap a^*c^*$ would also be regular. But this intersection is equal to $K$.