Convert the following CFG$\text{'}$s to CNF$.$

$SSS|a$

$S$aSa$|SSa|a$

$S$axx

$xaS|bS|a$

$EE+E$

$EE**E$

$E(E)$

$E7$

The terminals here are $+**()7.$

$S$ABABAB

$Aa|$

$Bb|$

Note that $$ is a word in this language but when converted into CNF

the grammar will no longer generate it$.$

$,S$SaS$|SaSbS|SbSaS|$

$SAS|SB$

$ABS|SA$

$BSS$

$Sx$

$xY$

$YZ$

$Zaa$

$SSS|A$

$ASS|AS|a$

$($i$)$ Find the leftmost derivation for the word abba in the grammar:

$SAA$

$AaB$

$BbB|$

$($ii$)$ Find the leftmost derivation for the word abbabaabbbabbab in the

CFG:

$SSSS|axb$

$xba|bba|abb$