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.

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

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

Q1 The finite automaton M_a is written formally as M_a = {Q, , , q₀, F} = {{00, 99}, {0, 1}, {((00, 0), 00), ((00, 1), 99), ((99, 0), 00), ((99, 1), 00)}, 00, {99}}. How many words does M_a accept? [1 mark]

Q2 The finite automaton M_b is written formally as M_b = {Q, , , q₀, F} = {{01, 99}, {0, 1}, {((01, 0), 01), ((01, 1), 01), ((99, 0), 01), ((99, 1), 01)}, 99, {99}}. How many words does M_b accept? [1 mark]

Q3 Let L = {0ⁱ1^j : i < j}. Construct a context-free grammar that generates L. [3 marks]

Q4 Construct a pushdown automaton that accepts (recognises) L. [3 marks]