Consider the CFG

(i) Prove that X can generate any b*.
(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's with the following exception: We consider the word A to have an even number of a's, as do all words with no a's, but of the words with no a's only Λ can be generated.
(v) Show how the difficulty in part (iv) can be alleviated by adding the production

S → XS

Transcribed Image Text:

S→SS | XaXaX | A X→bX A