- 4 Consider The Cfg S Ss Xaxax A X Bx A I Prove That X Can Generate Any B Ii Prove That Xaxax Can Generate Any 1 (489.81 KiB) Viewed 38 times
4. Consider the CFG S→SS | XaXaX | A X→bX A (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 ▲ 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 A can be generated. (v) Show how the difficulty in part (iv) can be alleviated by adding the production S→XS