I am trying to prove that L = { aNbMaN-M|N>=M>=0} is not regular using the pumping lemma.
I am pretty confused how to solve this. What I have so far (which I am not sure is right) is:
Assume L is regular. Let p>=1 be the pumping length. Then by the pumping lemma there exists p|=1. Consider the string s=ap+1bpap+1-p
From the pumping lemma we know:
1. s=xyz
2. y!= ϵ
3. |xy|<=p
4. for i>=0, xyz ϵ L
Then, sϵL and |s|=(p+1)+(p)+(p+1-p) = 2p+2>=p (I'm not sure that this is true though…)
By 1, s can be written as s=xyz. Since 3, |xy|<=p the string y contains only a's (How does this actually prove that y only contains a's?)
Since y!=ϵ, y contains at least 1 a.
I am unsure as to how to solve from here. Am I on the right track? I don't really understand how to proceed from this point or if my reasoning up to this point is correct. Any insight would be greatly appreciated!
Best Answer
Starting with $a^{p+1}$ automatically qualifies your $|xy| > p$, which is invalid. So let $p$ be the pumping length, and we want $|xy| \leq p$.
Let $a^{n}b^{m}a^{n-m} \in L$ be your string. Suppose $n + m \leq p$. So let $x = a^{n}$ and $y = b^{m}$. Now try pumping $(b^{m})^{i}$. Where is your contradiction?
Similarly, consider $x = a^{n-1}$ for $k < a$ and $y = ab^{m}$. Now pump $y$. Again, you get a contradiction when looking at $a^{n-m}$.
The intuition behind the pumping lemma is that FSA cannot count; and so, any language with a requiring you to count something (like this language or $L = \{ 0^{n} 1^{n} : n \in \mathbb{N} \})$ will not be regular.