T Naughton, CS NUIM

Remove everything from your desk except pens/pencils. Paper will be provided. Turn off all computer monitors. Answer all questions. Remember to be mathematically precise in all of your answers. You have until 10:50. You can leave whenever you are finished.

Note: The second half of this lab session (11:00 to 12:00) will be for any students who'd like help with any questions from last week's TM programming lab sheet, or who'd like help with the questions asked in this lab test.

Name......................................... Student number.........................

Course/year...................................

Answer Q1, Q2, and EITHER Q3A OR Q3B. If you insist on answering both Q3A and Q3B, you may be given the lower of your two marks.

Let L = {w#c : w {0, 1}*, c {0, 1}, c occurs exactly three times in w}.

Q1 Prove that L is context-free. [3 marks]
[Hint: A PDA or CFG is required here. Don't forget to add a sentence at the beginning of your proof explaining what you are doing, e.g. "We will prove that L is context-free by constructing a PDA that accepts L (or a CFG that generates L)," and a sentence at the end explaining how what you have done proves it is context-free, e.g. "This PDA recognises L (or this CFG generates L). Since there is a theorem that states that a language is context-free if and only if it is recognised by a PDA (or generated by a CFG), then this proves that L is context-free."]

Q2 Prove that L is decidable. [3 marks]
(Hint: A deciding TM is required here. Since you weren't specifically asked for the table of behaviour, the kind of pseudocode TM programming we did in the previous lecture will suffice. Don't forget to add suitable sentences at the beginning and end of your proof.)

Q3A Prove that L is regular. [3 marks]
(Hint: A FA (or NFA or regular expression) is required here. Don't forget to add suitable sentences at the beginning and end of your proof.)

Q3B Prove that L is not regular. [3 marks]
(Hint: A pumping lemma proof is required here. Because this is a short test, you can choose to fill in the blanks in the following proof template to speed you up.)

Proof. We will assume that L is regular to obtain a contradiction. Let p be the pumping length given by the pumping lemma. We choose w =                                           . Since w L and |w| p then the pumping lemma guarantees that w can be broken up into three pieces xyz such that if the y part is pumped zero or more times (and the two other conditions y e and |xy| p hold) then the resulting word is also in L. There are               different ways that w could be broken up into xyz. We investigate if any of these ways allows our w to be pumped as specified by the pumping lemma.

We have tried all possibilities, and there is no way that our w can be broken up into xyz satisfying the conditions of the pumping lemma. A contradiction. Our assumption must have been incorrect. This proves that L is not regular.