Newbie Question formal languages N-1 for a language typ 3

Question

I have the following problem: If I have a Grammar G with (Vn, Vt, P, S) Vn ={S}, Vt = {0} P: S -> 0S S -> 0

Why is the derivation from G: 0^(n-1)S? S => 0S => 00S => ... => 0^(n-1)S => 0^n

Is it because of epsilon?

Answer 1

The derivation you give is a derivation of $0^n$. It first uses $(n-1)$-times the rule $S \def\To{\Rightarrow}\To 0S$ that gives $$ S \stackrel{(1)}\To 0S \stackrel{(2)}\To 00S \To \cdots \stackrel{(n-1)}\To 0^{n-1}S $$ and then once the rule $S \To 0$. To give $$ S \To^* 0^{n-1}S \To 0^{n-1}0 = 0^n $$ Note, that you do not have a rule $S \To \epsilon$ in your grammar.