Explore the notion of Chomsky normal form in the following way. (a) Show that the grammar G with  and rewrite rules: is not in Chomsky normal form. (b) Show that grammar And is in Chomsky normal form....

Explore the notion of Chomsky normal form in the following way.

(a) Show that the grammar G with
 and rewrite rules:

is not in Chomsky normal form.

(b) Show that grammar

And

is in Chomsky normal form.

(c) Show that G and G’are equivalent by converting the rewrite rules of G into those of Gin the following way. Note that the rules A → a and B → b of G are already acceptable. Now convert other rules of G appropriate for Chomsky normal form. First replace S → bA in G by S → CbA and Cb → b. Likewise, replace A → aS by A → CaS and Ca → a. Continue in this way, keeping in mind the final form of the rewrite rules of G’.

(d) Give a derivation of