T Naughton, CS NUIM, Back to CS403 home

Remove everything from your desk except pens/pencils. Paper will be provided. Answer all questions. Remember to be mathematically precise in all of your answers. You have until 13:50. You can leave whenever you are finished. Write your name and student number below.

Name......................................
Stream (CS/CSSE/MCompSci).................. Student number..........................

Q1 Let L={w : wÎ{a, b}*, w=w^R}. Prove that L is a context-free language by constructing the state diagram of a pushdown automaton (PDA) that accepts L. [3 marks]

Q2 Define the language L from Q1 using a context-free grammar (CFG). [2 marks]

Q3 The language L from Q1 absolutely requires a nondeterministic PDA. It cannot be accepted by a deterministic PDA. You are required to modify the definition of L by adding some symbols to every word in L such that this new language can be accepted by a deterministic PDA. Define this new language using a CFG. [2 marks]

Q4 Prove that the intersection of the context-free languages and the recursively enumerable languages is nonempty. The only facts you can use are those that you have proved from above, and the following:

(i) Definition. A language is recursively enumerable iff it is accepted by a Turing machine.
(ii) Definition. A language is a CFL iff it can be generated by a CFG.
(iii) Theorem. A language can be accepted by a PDA iff it can be generated by a CFG.