$1.$ Consider the CFG:

S$--$ aS I bb

Prove that this generates the language defined by the regular expression

a$*$bb

$2.$ Consider the CFG:

S $--$ XYX

X aX I bXI A

Y $--$ bbb

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$)*$

$3.$ Consider the CFG:

S$--$ aX

X$-$ aX I bX IA

What is the language this CFG generates?

$4.$ Consider the CFG:

S $--$ XaXaX

X aX I bX IA

What is the language this CFG generates?

$5.$ Consider the CFG:

S $-$SS I XaXaX I A

X$--$ bXI A

$($i$)$ Prove that X can generate any b$*.$

$262$ PUSHDOWN AUTOMATA THEORY

$($ii$)$ Prove that XaXaX can generate any b$*$ab$*$ab$*.$

$($iii$)$ Prove that S can generate $($b$*$ab$*$ab$*)*.$

$($iv$)$ Prove that the language of this CFG is the set of all words in $($a $+$ b$)*$

with an even number of a$\text{'}$s with the following exception: We consider

the word A to have an even number of a$\text{'}$s$,$ as do all words with no

a$\text{'}$s$,$ but of the words with no a$\text{'}$s only A can be generated.

$($v$)$ Show how the difficulty in part $($iv$)$ can be alleviated by adding the

production

S$--$ XS

$6.($i$)$ For each of the CFG$\text{'}$s in Problems $1$ through $5$ determine whether

there is a word in the language that can be generated in two

substantially different ways. By "substantially," we mean that if

two steps are interchangeable and it does not matter which comes

first, then the different derivations they give are considered "substantially the same" otherwise they are "substantially different."

$($ii$)$ For those CFG$\text{'}$s that do have two ways of generating the same word,

show how the productions can be changed so that the language generated stays the same but all words are now generated by substantially

only one possible derivation.

I want the answer of Qno $6$