PROBLEMS

Consider the CFG:

$SaS|bb$

Prove that this generates the language defined by the regular expression

$a^{**}bb$

Consider the CFG:

$SxYx$

$xax|bx|$

$Ybbb$

Prove that this generates the language of all strings with a triple $b$ in

them, which is the language defined by

$(a+b)**bbb(a+b{)}^{**}$

Consider the CFG:

$Sax$

$xax|bx|$

What is the language this CFG generates?

Consider the CFG:

$S$xaxax

$xax|bx|$

What is the language this CFG generates?

Consider the CFG:

$SSS|xaxax|$

$xbx|$

$($i$)$ Prove that $x$ can generate any $b^{**}.$