# 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

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?

• Possible duplicate of How to prove that a language is context-free? Mar 25 '17 at 10:02
• Use the pumping-lemma Mar 25 '17 at 16:01
• @ Polygnome we can't use pumping -lemma to show language is context free (it is a necessary condition not sufficient)
– user35837
Mar 26 '17 at 6:33

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 xs or entirely of ys, 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.