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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

End of proof.

  • $\begingroup$ Thank you for your explanation. Now I see i had to study about it much more... $\endgroup$ – MatNovice Jun 3 '17 at 1:40
  • $\begingroup$ You are welcome :-) $\endgroup$ – Nicolas FRANCOIS Jun 3 '17 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.