Q$1(10$ points$)$

Consider the CNF for NONULLEVENPALINDROME $($EVENPALINDROME with$-$

out $lon)$ given below

$SAx|BY|AA|BB$

$xSA$

$YSB$

$Aa$

$Bb$

$(4$ points$)$ Show that this CFG defines the language it claims to define.

$(3$ points$)$ Find all the derivation trees in this grammar that do NOT have

a self$-$embedded nonterminal.

$(3$ points$)$ Find a derivation tree that contains a self$-$embedded nonter$-$

minal.