I have completed a), b) and c), I need help with d) onwards.

Question 1: FSAs, Regular Expressions, transformations Consider the following finite-state automaton A over = {0,2,4}: A = (2, {90, 91, 92, 93}, 8, 90, {92}) where 8 = {(90,0,91), (90,0, 92), (90, 4, 93), (91, 2, 91), (91, 2, 92), (92, 4, 92), (92, 2, 93), (43, 2, 92)}. (a) Draw the automaton A as a transition graph. [3 marks] (b) Give three words contained in the language accepted by the automaton A, and three words not contained in the language. All words should be over the alphabet E. [3 marks) (c) Explain what makes the automaton A non-deterministic. [2 marks] (d) Give, as a transition graph, a deterministic FSA accepting the same language as A. Justify your answer, e.g. by following the subset construction. [8 marks] (e) Give, as a transition graph, the minimal deterministic FSA accepting the same language as A. Justify your answer, e.g. by following the marking table construction. [8 marks] (f) Give a regular expression for the language accepted by the automaton A. Justify your answer, e.g. by following the state-elimination procedure. [8 marks] (g) Consider now the following FSA B with e-transitions, over the alphabet ? = {0,2,4}. Compute an equivalent FSA without E-transitions. 0 4 0 2 90 91 92 E E Justify your answer, e.g. by following the epsilon-removal construction. [8 marks] (h) Consider now the regular expression over the alphabet = {0,2,4}: (42)* 0 2* 0 (4 + 2)* Give, as a transition graph, an FSA (possibly with e-transitions) recognising the same language as the regular expression. 42 Note that you cannot use compound transitions e.g. of the form qo 91 [6 marks] (i) Syntactically different regular expressions may represent the same language. Consider regular expressions over = {a,b} . Which of the following equations hold? 1. E + a= a + 3. b(a + b)*b = ba*b+bb*b 2. b + bb* = 6* 4. (ab+b)* = ((ab)**) * Briefly justify your answers. [8 marks] 2