$($ii$)$ Prove that xaxax can generate any $b^{**}b{b}^{**}a{b}^{**}.$

$($iii$)$ Prove that $S$ can generate $(b**a{b}^{**}a{b}^{**}.$

$($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 $$ 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 $$ can be generated.

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

production

$SxS$

$($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 "sub$-$

stantially 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 gen$-$

erated stays the same but all words are now generated by substantially

only one possible derivation.

Consider the CFG:

$S$xbaax$|ax$

$xxa|xb|$

What is the language this generates? Find a word in this language that can

be generated in two substantially different ways.

$($i$)$ Consider the CFG for "some English" given in this chapter. Show

how these productions can generate the sentence:

Itchy the bear hugs jumpy the dog.

$($ii$)$ Change the productions so that an article cannot come between an

adjective and its noun.

$($i$)$ Show how in the CFG for "some English" we can generate the

sentence:

The the the cat follows cat.

$($ii$)$ Change the productions so that the same noun cannot have more than

one article. Do this for the modification in Problem $8$ also.