Paper 3, Section I, 4H
Part II, 2017
(a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Give an example, with justification, of a context-free language (CFL) which is not defined by any CFG in CNF.
(b) Show that the intersection of two CFLs need not be a CFL.
(c) Let be a CFL over an alphabet . Show that need not be a CFL.