I) Convert the following grammar

S abAB | abB

A bAB | bB

B Baa | Ba | A |

a- Eliminate -productions

b- Eliminate unit productions

c- Convert the resulting grammar into Chomsky Normal Form

II)

a) Write a regular expression for all strings of 0s and 1s having an even number of 0s. Does every string denoted by your expression have an even number of 0s? Is every string with an even number of 0s included in your regular expression? b) Write a regular expression for all strings of 0s and 1s in which all 0s occur before any 1s. c) Write a regular expression for all strings of 0s and 1s that are of odd length 4 .