i am trying to find a cfg for this cfl

L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$

is there a way to count the number of 0's or 1's in the string?

  • $\begingroup$ That question restricts its answer to a particular grammar. Hence, it could be argued this question is not a complete duplicate. My answer below cannot fit that question, either. $\endgroup$ – John L. Jan 10 '19 at 6:20
  • 1
    $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Jan 10 '19 at 7:36
  • 1
    $\begingroup$ @Apass.Jack It's less important whether the question is the same but whether this one has an answer there. Note that it is also possible that a set of questions completely answers a new one, in which case we'd also close as "duplicate". $\endgroup$ – Raphael Jan 10 '19 at 7:37
  • $\begingroup$ @Raphael, suppose I agree to all you have said. Does it mean that I should not post my answer below in the first place? It looks like my answer is different enough from all other answers reachable by this duplicate link. $\endgroup$ – John L. Jan 10 '19 at 8:02

The question defining a context-free grammar for $\{\in\{0,1\}^*:\#_0(w)=\#_1(w)\}$ restricts its answers to one particular grammar and the proof for its correctness is somewhat involved. Here I would like to show a different grammar that is easier to figure out.

Since the requirement is the same number of 0's and 1's, we can grow the start non-terminal $S$ by a pair of 0 and 1 in all sorts of way. (This is more or less what your idea of "counting" should be). We will have the following production rules, $S\to S01\mid S10\mid 01S\mid 10S\mid 01S\mid 10S\mid \epsilon.$

However, if we check closely, the above grammar does not generate 00111100. What happens is that the above grammar will generate the first part 0011 as a whole, missing the second part 1100. That suggests us to add another rule $S\to SS$. Once we have added that rule, rules $S\to S01\mid S10\mid 01S\mid 10S$ become redundant. The final grammar is $$S\to SS\mid 0S1\mid 1S0\mid \epsilon.$$

It is clear that the word generated by that grammar has the same number of 0's and 1's.

Are all such words generated by that grammar?

The rule $S\to\epsilon$ show that unique word of length 0 can be generated.

As the induction hypothesis, suppose all words of length less than $2n\le2$ can be generated.

Let $w$ be such a word of length $2n$.

Let $d(k)$ be the difference of the number of 0's and the number of 1's in the first $k$ letter of $w$. In particular, $d(2n)=0$. Since the situation is symmetric with respect to 0 and 1, WLOG assume $w$ starts with a 0, i.e., $d(1)=1$.

  • If $w$ ends with a 1, then $w=0w'1$ for some word $w'$. $S$ generates $w$ since $w'$ have the same number of 0's and 1's and $w'$ is shorter than $w$. So $S\Rightarrow0S1\Rightarrow0w'1=w$.
  • If $w$ ends with a 0, then $d(2n-1)=-1$. Since $d(x)$ changes 1 by 1, $d(k)=0$ for some $1\lt k\lt 2n-1$. Let $w_1$ be the first $k$ letters of $w$ and $w_2$ the rest of $w$. By induction hypothesis, $S\Rightarrow w_1$ and $S\Rightarrow w_2$. Hence $S\Rightarrow SS\Rightarrow w_1w_2=w$.

We have completed mathematical induction. All such words can be generated.


S → B1S | S1B | 1SB | 1BS | BS1 | SB1 | ɛ

B → 0

Basically, this is it. For every 1 it puts, it says that there have to be a derived 0 in the string, so it stays balanced. Every order of 1's and 0's can be derived.

  • $\begingroup$ This grammar does not generate 00111100. $\endgroup$ – John L. Jan 10 '19 at 8:27

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