Context$-$Free Grammars

List all elements of the Language, $L(G),$ of the following context$-$free grammars, G$.$

a$)$

$a$

Construct a context$-$free grammar for the following languages over the alphabet $=\{a,b\}.$

a$)L(G)=\{waab{w}^R|win{}^{**}\}$

b$)L(G)=\{b^2{a}^{n}b|ninN\}$

for each of the following regular expressions, $,$ construct a context$-$free grammar, $G,$ which pro$-$

duces the same language, i$.$e$.L(G)=L().$

a$)a(b{)}^{**}$

b$)(a(abaa)(b{)}^{**})$

Pushdown Automata

Construct Pushdown Automata for the following context$-$free languages over the alphabet $=$

$\{a,b\}.$

a$)L(M)=\{a^{n}b{b}^{2n}|nin{Z}^{{?}^{?}}n0\}$

b$)L(M)=L(G),G=(\{S,A\},\{a,b\},R,S),R=\{Se,S\frac{}{a}bS,SA,Ab\}$

Determine if the following strings are accepted by the pushdown automaton M$.$ If it is accepted,

also show a trace of the automaton $($i$.$e$.$ a sequence of state $/$ stack $/$ input tape triples$)$ that ends in

an accepting configuration.