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

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?

• How exactly do you produce 0101? Show me. Dec 4, 2023 at 13:23
• @gnasher729 That's the problem, I don't exactly get it but this is what I found on the internet. S -> 0S -> 0S1 -> 01S1 -> 010S1 -> 0101. What's bugging me is the step from 0S1 to 01S1, since there is no step from S to 1S Dec 4, 2023 at 13:26
• The longer I think about it, the more the derivation to 0101 seems incorrect. Could my answer be correct? Dec 4, 2023 at 13:33
• Looks like you asked ChatGPT. That step is absolute nonsense. There is no way to get to 0101. Yes, your answer was correct. Dec 4, 2023 at 13:34
• @gnasher729 it's weird that in the youtube video from "Easy Theory" he uses a different approach which is overcomplicating the problem. He solves it with: S -> 0S | P P -> 1P | \epsilon. But thanks! Dec 4, 2023 at 13:36

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}$$.