CISC $603$ M$6$ HW

Simplification and Normal Forms

Linz Section $6\mathrm{.}1$ exercises $1,2,4,6$

Eliminate the variable $B$ from the grammar

$S$aSB$|bB|$

$BaA|b.|$

Show that the two grammars

$S$abAB$|ba,|$

$A$aaa,

$BaA|bb|$

and

$S$abAaA$|abAbb|ba,$

$A$aaa

are equivalent.

$4.$ In Example $6\mathrm{.}1,$ show a derivation tree for the string ababbac, using both the original and the modified grammar.

$6.$ Eliminate all useless productions from the grammar

$SaS|AB|,$

$AbA,$

$BAA.$