PROBLEMS

Each of the following CFG$\text{'}$s has a production using the symbol $$ and yet

$$ is not a word in its language. Using the algorithm in this chapter, show

that there are other CFG$\text{'}$s for these languages that do not use $-$productions.

$Sax|bx$

$xa|b|$

$Sax|bS|a|b$

$xax|a|$

$SaS|bx$

$xax|$

$S$xax$|bx$

$x$xax$|xbx|$

Show that if a CFG does not have $-$productions then there is another

CFG that does have $-$productions and that generates the same language.

CHOMSKY NORMAL FORM

Each of the following CFG$\text{'}$s has unit productions. Using the algorithm pre$-$

sented in this chapter, find CFG$\text{'}$s for these same languages that do not have

unit productions.

$Sax|Yb$

$xS$

$YbY|b$

$SAA$

$AB|BB$

$B$abB$|b|bb$

$SAB$

$AB$

$BaB|Bb|$