Amusing Exam Content
From the sample final for the class I'm marking:
1a) Is this given language (which I shall not type out here) context-free? If so, provide a context-free grammar. If not, prove that it isn't.
1b) Prove that the problem of determining whether a given language is context-free is undecidable.
1c) Given (b), is (a) a fair question to ask on an examination? Explain your answer.
The answer to 1c is, of course, yes. The reasons for this are actually fairly subtle.