Show that the language $\{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$ is not regular using the Pumping Lemma

Question

I have got a question. I have to proof that the given language is not regular and I am not sure I am doing it correct.

The language is:

$ L = \{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$

So using pumping lemma I will show that given language is regular. I take a string $ s =a^nb^nbb, s \in L$

Then by pumping lemma $s = xyz$ I divide my string to $x = a^n, y= b^n , z=bb $

So now I can take string $ s = xyyz $ and we see now that there will be more b letters in word than a generated by power so the rule $ \#w_b = \#w_a + 2 $ is broken. So by pumping lemma given language is not regular.

If you could check if I am doing it correct, I will be very thankful.

Answer 1

More precisely : let $N$ be the number of states of a FSA recognizing your language $L$. Then for any word longer than $N$ recognized by your FSA, there are three words $x$, $y$ and $z$ such that :

• $|y|\ge1$
• $|xy|\le N$
• for all $n\in\mathbb N$, $xy^nz\in L$.

Now consider $a^Nb^{N+2}$. As it is larger than $N$, it can be cut in three words : $$a^Nb^{N+2}=xyz$$ As you have $|xy|\le N$, $y=a^k$ for some $k\ge1$. But then $$xyyz=a^{\alpha}a^{2k}a^{N-\alpha-k}n^{N+2}$$ doesn't belong to your language $L$, because $\#a+2=N+k+2\ne N+2=\#b-2$.

End of proof.