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

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.

• In pumping lemma, you can't "choose" where you want to cut your word. It says : "There exists three words $x$, $y$ and $z$ such that for all $n$, $xy^nz$ is an accepted word". It doesn't say "for all cutting $xyz$ of your word, $xy^nz$ is accepted. – Nicolas FRANCOIS Jun 3 '17 at 1:07

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