$[5$ marks$]$ Convert the following grammar to be in Chomsky normal form.

$S$ABD,$AS,BD,Dda$

$,Aab,Bbd,B$

$[4$ marks$]$ Let $M=(Q,,,q_0,F)$ be defined as the following DFA, where

$=\{0,1\},Q=\{q_0,q_1,q_2\},$ with $q_0$ the start state, $F=\{q_2\},$ and transition

function $$ given as a table below.

The language aceepted by $M$ is described by the regular expression $0^{**}{1}^{+}.$

Convert DFA $M$ to a context$-$free grammar that generates the same language.

$[5$ marks$]$ Convert the CFG from Question $2$ to a pushdown automata

given as a state diagram that recognizes the same language.

$[3$ marks$]$ Let $E=\{a^i{b}^j|ij\}.$ Show that $E$ is a context free language.

$[3$ marks$]$ Demonstrate that the set of context$-$free languages is not closed

over the operation of intersection. Use $\{a^n{b}^n{c}^n|n0\}$ is not context free.

$[6$ marks$]$ Prove that the following two different versions of pushdown

automata machines are equivalent:

$(1)$ the PDA must have an empty stack, consume all input, and be at an

accept state in order to accept an input word;

$(2)$ the PDA is allowed to have a non$-$empty stack, but consume all input,

and be at an accept state in order to accept an input word.

$($Hint: you need a dollar sign to help mark the bottom of the stack!$)$