Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
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
1  
@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
1  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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