How to solve pumping lemma questions? 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!
 A: 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.
A: Sarah, you're on the right track. Actually, you're one step away from proving the nonregularity of the language, but you have a mistake (or omission) in the expression of the pumping lemma.

From the pumping lemma we know: 1. s=xyz 2. y!= ϵ 3. |xy|<=p 4. for i>=0, xyz ϵ L

Your (4) should be: for $i \geq 0, xy^iz\in L$

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?)

Well, the string $s$ you've chosen is $a^{p+1}b^pa^{p+1-p}$, or simply $a^{p+1}b^pa$. Then, since $|xy| \leq p$, all of the symbols in both $x$ and $y$ must come from the first $p$ symbols in $s$. What are they?
Now, using the fourth step with different values for $i$, what kind of strings do you get? Do they remain in the same language $L$?
