$5$ a Consider the grammar with the two productions

$SlongrightarrowSSS{a}^a$

Show that the number of distinct leftmost derivations of $a^n$ is given by $x_n={\displaystyle \underset{\{\begin{array}{c}\text{:}[i+j=n]\\ i0\\ j0\end{array}}{\overset{?}{}}}{x}_i,x_j$

where $x_1=1.$ Show that

$x_{n+1}=\frac{1}{n+1}([2n],[n])$

b Show that every linear language without $e$ has a grammar in which each production is of one

ofthe forms

AlongrightarrowaB,AlongrightarrowBa, $or$ Alongrightarrowa

please refer to the picture for clarification