Consider the following grammar with starting symbol of $S$.

$$S \rightarrow 0S11\;|\;S1\;|\;0$$

Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all $n\;\ge0$, every string of length $n$ in $L$ can be generated by the grammar.

I don't know how to start doing it. Any hints ? What I can think of is the base case which will be : Let $w$ be the string generated by the given grammar. If $n=1$, then $w=0$, which can be generated by applying the third rule.


Let's try induction. The base case is easy (although not as trivial as you write in your question).

Now, assume any word in $L\cap \{0,1\}^n$ is generated by $G$. Let's take a word $w$ in $L\cap \{0,1\}^{n+1}$ and show it is generated by $G$.

Assume $w=0^a1^b$. We know that $b\ge 2(a-1)$. Note that $0^{a-1}1^{b-1}\in L\cap \{0,1\}^n$ (i.e., $b-1\ge 2(a-2)$) so it must be generated by $G$ . Since there is only one terminal derivation $S\to 0$, this must be the last derivation. It follows that there must be a sequence of derivations in $G$ which looks like:

$$S \to^* 0^{a-2}S1^{b-1} \to 0^{a-1}1^{b-1}$$ with the last transition $S\to 0$. Here you need to explain why $0^{a-2}S1^{b-1}$ is the only possible sentinel phrase that yields $0^{a-1}1^{b-1}$ (and it can't be, e.g., of the form $0^{a_1}S0^{a_2}1^b$); This is a simple argument that I'll leave you to complete.

So if $S \to_{G}^* 0^{a-2}S1^{b-1}$ we can now take the second transition and then the third, and get $$ S \to^* 0^{a-2}S1^{b-1} \to 0^{a-2}S11^{b-1} \to 0^{a-2}011^{b-1} = 0^a1^b$$

and we are done.

| cite | improve this answer | |

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