2
$\begingroup$

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :)

Now my questions.

What is the easiest way to find a word, to start the Pumping Lemma? Are there some tricks I have to know? For example I wanted to prove the following language is non-regular: $$A=\{a^nb^mc^k\mid n,m,k \in N \wedge n\ mod\ 2=0=m\ mod\ 2\ \wedge m<k\}$$

My idea is to choose the word $w=c^n$. But it seems like a bad idea, because if I choose the decomposition $w=xyz$ with $y\not= \lambda$ than I can not pump it up, so that it isn't in A anymore. With the decomposition we get $x=c^i$,$y=c^j$ and ${c}^{n-i-j}$. Now I have to choose an $k$ to pump it up, but there is no $k$, were $w$ is not in $A$ anymore, or am I wrong?

For example let $k$ be $0$. Then we get $xy^0z = {c}^{n-j}. But $ m < k $ \Longleftrightarrow 0<n-j$ for $ j > 0 $ is not wrong, so its not working.

My goal is to find a smart word, so that I do not need a case distinction.

I hope my problem is understandable. If not just ask.

$\endgroup$
0
$\begingroup$

You are on the right track. You just need to continue observing and trying. The trials and errors you have done might have been done by many experienced users more or less in different ways.

As you have found $w=c^n$ does not work. That word is too simple to be pumped outside of $A$, whether we will pump it down or pump it up.

Let us continue your preference/acumen to ignore the $a^n$ part. Let us choose word $b^mc^k$, where $m<k$. If we can pump substring of $b^m$ enough time, the number of $b$'s in $w$ will become larger than $k$ eventually. To ensure what will be pumped is a substring of $b^m$, we can let $m\ge p$, where $p$ is the pumping length.

So let us try $b^{p}c^{p+1}$. I will let you check that this word, if pumped up, will be no longer in $A$.

However, the number of $b$'s in $w\in A$ must be even. If $p$ is odd, $b^pc^{p+1}$ is not in $A$ in the first place. Well, in that case, we can choose $b^{p+1}c^{p+2}$.

In general, how to choose the right word so that it could pump down or up out of the language might feel like a bit of black magic without much pattern initially. However, there is actually not much choices involved. You may learn from this answer and this answer.


Exercise. Prove the following language is not regular. $B=\{a^nb^mc^k\mid n,m,k \in N \wedge n\operatorname{mod}2=1=m\operatorname{mod 2}\ \wedge m<k\}$

$\endgroup$
  • $\begingroup$ Thank your for this answer I will try to understand $\endgroup$ – Sandruschka Jan 22 at 14:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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