Let $G=(V,,R,S)$ where the productions are:

$SAA$

$SB$

$A0A$

$AA0$

$A1$

$B0B00$

$B1$

$1$a$.$ Give V$,,R,S.$

$1$b$.$ Give the state transition diagram for the corresponding PDA.

$1$c$.$ Define $L(G)$ using standard set notation to characterize the strings in $L.$

$1$

$1$d$.$ Show a PDA trace $($just an accepting path$)$ for the string $s=00101.$

$2.$ Suppose the following FSA, $M,$ recognizes CNF sentences.

Figure $1$: State Transition Diagram for $M.$

$2$a$.$ Define the corresponding CFG for $M,G=(V,,R,S)($constructed using method in text$).$

$2$b$.$ Show the CFG derivation for string $s=(a1$vvnota$2{)}^{{?}^{?}}(a3$vva$4).$

$2$c$.$ Show the parse tree for $s$ defined in $2$ b$.$

$2$d$.$ Give the PDA, $P,$ corresponding to $G$ in $2a.$

$2$e$.$ Give a PDA computation sequence $($PDA trace$)$ for $P$ recognizing string $s$ defined in $2b.$

$3.$ Let encodes lists of natural numbers using unary representation and having only monotonically increasing lists of numbers