Prove that the context free grammar S --> aS | λ has the language {$a^n | n >= 0$}

Question

Here is what I have so far

Claim: For every string w E L1, S -->* w Proof: By induction on |w|

Basis: Suppose w is a string in L1 with length 0. Then w =λ, the empty string. Since S -->λ is a rule in R

S --> λ (using the rule S --> λ) as is required to establish the claim.

Inductive step: Let k be an integer such that k >= 0. For every integer h such that 0<= h <= k, and every string w E l1 with length h, S -->* w

Inductive claim: For every string w E L1, with length K+1, S -->* w Let w be a string in L1 with length k +1.

Now at this point I'm not sure exactly what to do next, I don't know how to finish this claim.

Answer 1

For your induction step you should be showing that if $S\Rightarrow^* a^n$ (your induction hypothesis), then $S\Rightarrow^* a^{n+1}$. And that’s straightforward: you have the production $S\to aS$, so you have a derivation

$$S\Rightarrow aS\Rightarrow^*aa^n=a^{n+1}\;,$$

where the middle step uses the induction hypothesis. You can now conclude that if $L$ is the language generated by the grammar, and $L_1=\{a^n:n\ge 0\}$, then $L_1\subseteq L$. To complete the proof, you must show that $L\subseteq L_1$, i.e., that every word in $L$ is of the form $a^n$ for some $n\ge 0$. I’ll sketch one way to do this.

If $L\nsubseteq L_1$, then $L\setminus L_1\ne\varnothing$. Let $w\in L\setminus L_1$ have minimal length amongst all words in $L\setminus L_1$.

• Show that $w\ne\lambda$.
• Conclude that $w$ has a derivation of the form $S\Rightarrow^*uS\Rightarrow uaS=wS\Rightarrow w$.
• Explain why $u\in L$. Observe that $u$ is shorter than $w$, and conclude that $u\in L_1$.
• Show that $w\in L_1$, thereby deriving a contradiction.