[Solved]: Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$

Problem Detail: 

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free grammar that describes this language. After defining a context-free grammar I want to formally prove that this context-free grammar describes this language.

I've came up with the context-free grammar production rules: $$ \begin{align*} &S\to0S1S \\ &S\to1S0S \\ &S\to\epsilon \end{align*} $$ Is this the correct context free grammar to define this language?

Im kind of stumped for the proving part. I'm guessing I will need some sort of induction?

Asked By : Andrew Reynolds

Answered By : FrankW

Your grammar does work. And you are correct in assuming that induction is a worthwile proof-technique. As a hint, you can use the following induction hypothesis:

IH: All the words of length at most $n$ that can be derived from $S$ have an equal amount of $0$'s and $1$'s.

Can you fill in the anchor and step from here?

---

As D.W. pointed out, the above is only enough to prove that the grammar will not produce any wrong words, or $L(G) \subseteq L$. In order to complete the proof, you also need to show that $L \subseteq L(G)$, i.e. all the words in the language are generated by the grammar.

For this part you can try an induction with the hypothesis

IH: All the words of length at most $n$ that have an equal amount of $0$'s and $1$'s can be derived from $S$.

(Of course, you can combine these two inductions, but having them seperate may be easier to handle if you are unexperienced.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22729