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 $Lcap {0,1}^n$ is generated by $G$. Let’s take a word $w$ in $Lcap {0,1}^{n+1}$ and show it is generated by $G$. Assume $w=0^a1^b$. We know that $bge 2(a-1)$. Note that $0^{a-1}1^{b-1}in Lcap {0,1}^n$ (i.e., $b-1ge 2(a-2)$) so it must be generated by $G$ . Since there is only one terminal derivation $Sto 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 $Sto 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
