Context free grammar $\{0^n 1^m : n,m \geq 0\}$

Question

I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$.

I thought that the simple answer would have the production rules: $S \rightarrow \epsilon \ | \ 0S \ | \ S1$

Since I thought this implies that whichever string you have, you can always place a $0$ in front of the string or a $1$ at the end of the string. However it seems that you can also create the string $0101$ with these production rules, could someone explain to me why my production rules won't give the desired outcome?

Answer 1

You can't produce $0101$ because every time you use $0S$ you are putting a $0$ at the beginning of the string. Whenever you want to insert a $1$, it directly goes to the end of the string and it will remain the last element of the string. This holds also in the opposite way. You can add $1$s and, if you add a $0$, it became the first element of the string and you can only add characters to the right of this $0$.

The proposed production rules are correct and it can be easily shown by induction on the number of times a production rule is applied $ \ell$.

The strings obtained by the production rules (starting from empty string) $S\rightarrow \epsilon \ | \ 0S \ | \ S1 $ are in the form $0^n1^m$.

a) Base case: $\ell=0$ this is true because $S=\epsilon = 0^0 1^0$.

b) Inductive step: Assuming the thesis true for $\ell$ applications of the production rules, we show it for $\ell +1$ applications. Assume $S$ is the results of $\ell$ applications of the production rules, thus, by inductive hypothesis $S=0^n1^m$. Now, we have three possibilities, one for each production rule:

1. $S\rightarrow \epsilon$, in this case the thesis remains true.
2. $S\rightarrow 0S$, then we added a starting $0$, so if by inductive hypotesis $S=0^n1^m$, we obtained $0^{n+1}1^m$.
3. $S\rightarrow S1$, as previous case, we obtain $0^n 1^{m+1}$.