A grammar is said to be in Chomsky Normal Form (CNF) if every production is either of the form A ->• BC or of the form A ->• a, where A, B, and C are nonterminals, and a is a terminal. Show how to...

A grammar is said to be in Chomsky Normal Form (CNF) if every production is either of the form A ->• BC or of the form A ->• a, where A, B, and C are nonterminals, and a is a terminal. Show how to convert any grammar into a CNF grammar for the same language (with the possible exception of the empty string — no CNF grammar can generate e).