How to solve pumping lemma questions?

Question

I am trying to prove that L = { a^Nb^Ma^N-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=a^p+1b^pa^p+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!

Answer 1

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.

Answer 2

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