[Solved]: Proving correctness of a CFG by induction on length of strings generated

Problem Detail: 

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.

Asked By : Altaïr

Answered By : Ran G.

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.

Best Answer from StackOverflow

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