Construct a derivation of $0^31^3$ using the grammar given in Example $5.$

EXAMPLE $5$

Give a phrase$-$structure grammar that generates the set $\{0^$n$1^$n $|$ n $=0,1,2,...\}.$

Solution: Two productions can be used to generate all strings consisting of a string of $0$s followed by a string of the same number of $1$s$,$ including the null string. The first builds up successively longer strings in the language by adding a $0$ at the start of the string and a $1$ at the end. The second production replaces S with the empty string. The solution is the grammar G $=($V$,$ T$,$ S$,$ P$),$ where V $=\{0,1,$ S$\},$ T $=\{0,1\},$ S is the starting symbol, and the productions are

S$->0$S$1$

S$->$

The verification that this grammar generates the correct set is left as an exercise for the reader.