Proving that grammar generates language with multi variable inequalities

Question

I am struggling with trying to come up with the inductive proofs to prove that the following grammar is equal to $ L = \{0^m1^n | m \leq 2n, n \leq 2m \}$

The grammar is

$ S → A \:|\: B $

$ A → 00A1 \:|\: C $

$ B → 0B11 \:|\: C $

$ C → 0C1 \:|\: ε $

How exactly do the proofs for proving $ L \subseteq L(G) $ differ from $L(G) \subseteq L$.

In specific, how do the inequalities affect the format of the inductive proof?

Answer 1

The grammar produces words that we can separate into two cases:

1. $S$ gets replaced by $A$, then the second rule is used $k\geq0$ times with the branch that keeps the $A$ present. Then it is used with the branch that replaces $A$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{2k+r}1^{k+r}$.
2. $S$ gets replaced by $B$, then the third rule is used $k\geq0$ times with the branch that keeps the $B$ present. Then it is used with the branch that replaces $B$ by $C$. Finally, the last rule gets used $r\geq0$ times with the branch that keeps the $C$ present, followed by the branch that replaces it with the empty word. This generates words of the form $0^{k+r}1^{2k+r}$.

In the first case $m=2k+r,n=k+r$ satisfy $m=2k+r\leq 2(k+r)=2n$ and $n=k+r\leq 2(2k+r)=2m$. In the second case $m=k+r,n=2k+r$ satisfy $m=k+r\leq 2(2k+r)=n$ and $n=2k+r\leq 2(k+r)=2m$. Therefore, all words produced by the grammar belong to $L$.

---

Now, suppose that you take a word in $L$. This would be a word of the form $0^m1^n$ with $m\leq 2n$ and $n\leq 2m$. As before, let's separate the analysis in two cases:

1. Assume that $m\geq n$. Define $r=2n-m$. Observe that since $m\leq 2n$ we have $r\geq0$ and that $r\leq n$, since $m\geq n$. Define $k=n-r=m-n$ and note that $m-r=2(m-n)=2k$. Therefore, $0^m1^n=0^{2k+r}1^{k+r}$. Now you can see how to produce this word using the grammar by following the flow in case 1 above.
2. Assume that $n<m$. Define $r=2m-n$. Observe that $r\geq$, since $n\leq 2m$ and that $n-r=n-m\geq0$. Define $k=n-m$. Then $m=k+r$ and $n=2k+r$. Therefore, $0^m1^n=0^{k+r}1^{2k+r}$. Now you can see that you can produce this word using the grammar as in case $2$ above.