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 11:50. You can leave whenever you are finished.

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

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

Q1 What is the tenth word in the lexicographical ordering of the language accepted by FA M given by the following state diagram?

Answer:                                 [1 mark]

Q2 The finite automaton M_a is written formally as M_a = (Q, , , q₀, F) = ({00, 99}, {a, b}, {((00, a), 99), ((00, b), 00), ((99, a), 99), ((99, b), 00)}, 00, {99}). Write this finite automaton as a state diagram. [1 mark]

Q3 Fill in the blank (but don't use a regular expression): the language that M_a accepts is L(M_a) = { w :

}. [1 mark]

Q4 Fill in the blank: a regular expression that describes the language L(M_a) is

. [1 mark]

Q5 Construct a FA that accepts the language L = {w : w {0,1}*, w contains at least two 0s and w ends with 11}. You can either give a formal definition or give a state diagram. [3 marks]

Q6 Give a regular expression that describes L:

[3 marks]

Q7 Construct a FA that accepts the language L' = {w : w {0,1}*, w does not begin with 01 or 10}. You can either give a formal definition or give a state diagram. [3 marks]

Q8 Give a regular expression that describes L':

[3 marks]

Q9 Construct a regular expression that describes the language accepted by the following FA.

Answer:                                 [2 marks]

Q10 Use this sequence of steps (given in lectures) to construct an equivalent FA for the following NFA. (Do not remove unused/useless states. Do not simply figure out the language and write the FA from scratch.) [2 marks]

Q11 Let L₁ = {a, ab} and let L₂ = {e, 1, 00}. Assume that in lexicographical order the union of the two underlying alphabets is {0, 1, a, b} (i.e. word a1 comes before word aa in lexicographical order). Write out the first ten words in the lexicographical ordering of (L₁*) L₂. [3 marks]