Q$1.$ Construct a Context Free Grammar for each of the following languages:

$L=\{a^n{b}^m{c}^{2n+2n}|n0,m0\}$

$|=2j$ or $\{$:$j=2k\}$

$L=\{0^n{1}^m|nm2n\}$

Q$2.$ Consider the following Context Free Grammar $($ S is the start variable$)$:

$SA1B$

$AOA|||$

$B0B|1B|$

Give the leftmost and the rightmost derivations of the string $00011$ and draw its parse tree.

Q$3.$ Consider the following Pushdown Automata $($the initial stack variable is $$).$

$xx$

$1,$$$$

Starting from the initial instantaneous description $(q,0011,$ $$),$ show all the reachable instantaneous descriptions $($see Figure $6\mathrm{.}3$ on page $231$ of the book$).$

Q$4.$ Convert the following Context Free Grammar into Chomsky Normal Form $($ S is the start variable$).$

$S$OAO$|1B1|BB$

$AS|||$

$BS|A||$