Paper 3, Section I, 4H

Automata and Formal Languages
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 LL be a CFL over an alphabet Σ\Sigma. Show that Σ\L\Sigma^{*} \backslash L need not be a CFL.