Note Diagrams and execution traces may be scanned, but everything else must be typed. This is to allow automated checking for plagiarism, and to ensure that we can read your work. Question 1 Languages and automata (20 marks) (a) The following is an NFA over the alphabet {a,b}. a 8 b 3 b Determinize it using the algorithm taught in lectures. (The DFA that you give need not be total.) Briefly explain the initial state of your DFA, and the a-labelled transition from it. [5 marks] (b) Prove that the following language over the alphabet I = {a, b} is non-regular. L = {b5p+qabp.9 N} Do not use the Pumping Lemma (a topic that has not been taught in this module). [5 marks] (c) The following is a partial DFA over the alphabet I = {a,b}. Make it into a total DFA (using the algorithm taught in lectures), and then prove that what you have obtained is minimal [5 marks] 10 13 14 a 16 b b 11 12 15 5 a