0
$\begingroup$

This question already has an answer here:

One possible CFG containing twice as many zeros as ones can be,

S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ

(This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other possible CFGs can be S→ϵ|1S00S|00S1S|0S1S0|S00S1 or S→ϵ|1S00S|00S1S|0S1S0|01S0S which some might say is better because of less redundancy)

Now I want to prove that this grammar is correct. It involves two steps

1) Prove that all the strings generated by this CFG contain twice as many zeroes as ones.(Consistency)

2) All the strings containing twice as many zeroes as ones are generated by this grammar.(Completeness)

It is trivial to see that all the strings that this grammar generates, contains twice as many zeroes as ones.

The difficulty is in the second part. How to prove that this grammar generates all the strings containing twice as many zeroes as ones?

My solution: One way to do is to make cases.

Let's say $L$ be the language containing all the strings having twice as many zeroes as ones. If a string $s\in L $, that means

$f(s) = n_{0}(s) - 2*n_{1}(s) = 0$

Now let's say we are at origin on x-axis and we move 1 step step right if we encounter 0 and move two step left if we encounter 1. In the end we should end at origin because $f(s)=0$. Now taking cases like when we remain only right side of the origin, when we remain left side of the origin, when we cross the origin in between of the string we can prove that our grammar generate the string. (I am not going into detail as my problem is not related to this approach to the solution).

But I want to do it in more general way, without taking cases. Because I think that the general method in which we can prove it can be useful to prove the general question of grammar having 0s and 1s in ratio a:b, where a and b are any constants.

$\endgroup$

marked as duplicate by Raphael Apr 8 '16 at 6:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Welcome to CS.SE! Please see our reference question on this topic: cs.stackexchange.com/q/11315/755. I suggest you try to work through the approach described there, and if you're still not able to solve it, edit the question to show how far you got and where specifically you got stuck. $\endgroup$ – D.W. Apr 8 '16 at 5:19
  • $\begingroup$ Have you looked at the reference question? $\endgroup$ – Raphael Apr 11 '16 at 21:12
  • $\begingroup$ Yes. But still I am not able to solve. I think I need more time. $\endgroup$ – arman Apr 12 '16 at 9:10