How to choose a word to apply the Pumping Lemma?

Question

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.

Answer 1

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\}$