1
$\begingroup$

How would you go about proving that this Language is Context free. I'm having issues with drawing the PDA for this.

I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free.

I so far assume that when a string of 11s occur add x to the stack and when 010s add y to the stack, but I'm having issues drawing that part out the part were you check to see if the number of x's in the stack is greater then the number of y's.

Update based on GoodDeeds answer, just need to clearify something Basic PDA Input, Pop -> Push

"Whenever a 11 is encountered, and the top of the stack is not a y, push an x. Else, pop a y."

So in this case whenever a 11 is encountered do I draw out the transition like example A or B?

enter image description here

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How to prove that a language is context-free? $\endgroup$ – David Richerby Mar 25 '17 at 10:02
  • $\begingroup$ Use the pumping-lemma $\endgroup$ – Polygnome Mar 25 '17 at 16:01
  • 2
    $\begingroup$ @ Polygnome we can't use pumping -lemma to show language is context free (it is a necessary condition not sufficient) $\endgroup$ – Call_on_Duty Mar 26 '17 at 6:33
1
$\begingroup$

Sketch of an answer:

As you suggested, use the states of the PDA to check when a $11$ or a $010$ has been found. Then, instead of keeping track of the number of $11$s and $010$s separately, keep track of the difference in their numbers.

You could have some symbol in the stack initially, say, $\$$, to mark that the stack is empty. Then, use a symbol $x$ to denote $+1$ in the difference, and $y$ to denote $-1$ in the difference.

Whenever a $11$ is encountered, and the top of the stack is not a $y$, push an $x$. Else, pop a $y$.

When a $010$ is encountered, if the top of the stack is not an $x$, push a $y$. Else, pop an $x$.

Thus, at any given point, the stack consists entirely of $x$s or entirely of $y$s, or only the $\$$. The number of $x$s denotes how many more $11$s have been encountered as compared to the number of $010$s, and vice-versa.

At the end of the input, accept if the top symbol is an $x$, as this would mean that the number of $11$s were more than the number of $010$s.

| cite | improve this answer | |
$\endgroup$

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.