1
$\begingroup$

I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$.

I have this: By contradiction, if $L$ is context free, we use the pumping lemma, then let $N$, and $w = a^{floor(N/2)}*b^{floor(N / 2)}$, with $|w| = N$. Then if we divide $w = uvxyz$, with $v \not = \epsilon$ and $x = \epsilon$, we see that when repeating v there appear more a's than b's, then $uv ^ kxy ^ kz$ $\notin$ L. Contradiction.

This is right or am I missing something else?

Improve this question
$\endgroup$
2
$\begingroup$

This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +) } is a CFL

A PDA would work as follows :

On reading a :

If the stack is empty or the top of the stack is a push a

If the top of stack is b pop b push nothing

On reading b :

If the stack is empty or the top of the stack is b push b

If the top of stack is a pop a push nothing

At the end of input if stack is empty accept else reject

Improve this answer
$\endgroup$
  • $\begingroup$ Considering your proof , if we choose v to have only as and y to have only bs , and length of v is the same as y then the string can be pumped , similarly if you wish for y to be empty , you can choose v to be in the middle of the string with equal number of as and bs and still the string can be pumped , remember the pumping lemma needs us to show that there is no way to pump the string , not to show that there is a way by which it can't be pumped $\endgroup$ – Anazz Nov 8 '20 at 18:15
  • $\begingroup$ so the mistake is that we can keep pumping? $\endgroup$ – Johan C Nov 8 '20 at 19:29
  • $\begingroup$ The mistake is simply that there is a way to pump the string you provided depending on your choice of u,v,x,y,z , you may have provided a choice in which the string cannot be pumped but that is not enough , to say that a string cannot be pumped you need to show that any valid choice of u,v,x,y,z will not allow the string to be pumped only then can you say the string fails the pumping lemma and the language is not CFL , on the contrary for the string to pass the pumping lemma it is enough to provide a single choice of u,v,x,y,z which allows the string to be pumped $\endgroup$ – Anazz Nov 8 '20 at 21:23
  • $\begingroup$ As for how to pump the string this is explained in the first comment $\endgroup$ – Anazz Nov 8 '20 at 21:23

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.