$($a$)[2$ marks$]$ Convert the following CFG to an NPDA that accepts the same language, by

empty stack.

$S$aSb$|bSa|c|$

$($b$)[2$ marks$]$ Give a sequence of configurations to show how the string abcab is accepted

by your NPDA.

$($c$)[1$ mark$]$ Give an informal description of the strings that make up the language

generated by the grammar, or$,$ equivalently, the language accepted by your NPDA.

$11(5$ marks$)$

Convert the following grammar to Chomsky Normal Form $($CNF$),$ explaining each step.

$S$aSa$|B$

$BbbC|bb$

$CcC|$

$12(10$ marks$)$

$($a$)[5$ marks$]$ Draw an NPDA that accepts, by final state, the following language:

$L=\{a^n{b}^{n+m}{c}^m$:$n0,m1\}$

$($b$)[5$ marks$]$ Give a CFG for the language $L$ from part $($a$),$ and draw a parse tree for the

string $a^2{b}^{3}c$