# Prove that the language $L = \{a^nb^kc^{n+k} : n \geq 0, k \geq 0\}$ is not regular

Problem Prove that the language $L = \{a^nb^kc^{n + k} : n \geq 0, k \geq 0\}$ is not regular by Pummping Lemma.

Pumping Lemma Let $L$ be an infinite regular language. Then there exists some positive integer $m$ such that any $w \in L$ with $|w| \geq m$ can be decomposed as: $w = xyz$, with $|xy| \leq m$, and $|y| \geq 1$ such that $w_i = xy^iz,$ is also in $L$ for all $i = 0,1,2 \ldots$

Note:$|w|$ means the length of string $w$.

My attempt to this problem is as follows,

Let $m$ be any positive integer, we definie $w$, $w = a^mb^mc^{m+ m}$. Since $m > 0$ which implies $n \geq 0$ and $k \geq 0$ are true. Hence, $w \in L$.
Now consider $|xy|$, by Pumping Lemma we know that $|xy| \leq m$ which implies that $xy$ must consists of entirely $a's$. Furthermore, $|y| \geq 1$, hence $y = a^k$ for some positive integer $k$.
Assuming $k = 1$ to consider $w_0 = xy^0z = a^{m-1}b^{m}c^{2m}$, this string is obviously not in $L$ because $m - 1 + m \neq 2m$. Similarly for $k > 1$, we can always use $y^0$ to extract some a's from $a^m$ which contradicts the constraints $n + k$. Therefore $L$ is not regular $\square$.

Any suggestion or comment would be greatly appreciated. Thank you.

• It's generally fine, but $m$ cannot be any positive integer, it should be the $m$ of the pumping lemma. The proof should start: suppose $L$ were regular. By the pumping lemma, there exists an $m$ such that ... – Yuval Filmus Aug 9 '11 at 22:21
• Also, I don't think that there is any need to prove $w \in L$, it's immediate. – Yuval Filmus Aug 9 '11 at 22:22
• @Yuval Filmus: Thanks a lot. In fact, I wrote $m$ be a positive integer before. Shame on me. As for the proof of $w \in L$, I stated it clearly so I remember that I have to pick a $w \in L$, otherwise my proof is invalid. Lastly, a nice catch on "Suppose $L$ is regular". Would you mind changing your comment to answer so that I can accept it. Thanks in advance. – Chan Aug 9 '11 at 22:31
• If $L$ was regular, then its intersection with $b^{\ast} c^{\ast}$ would be regular. The intersection is $\{b^k c^k \colon k \geq 0\}$, which is a bit simpler, also nonregular language. – sdcvvc Aug 10 '11 at 20:58
• Note that you can use the contraposition of Pumping Lemma for a direct proof over all natural $m$. – Raphael Aug 10 '11 at 20:58

It's generally fine, but for one thing: $m$ cannot be any positive integer, it should be the $m$ given by the pumping lemma. The proof should start: Suppose $L$ were regular. By the pumping lemma, there exists an $m$ such that ... and so on.
Also, the proof of $w \in L$ is rather verbose.