a. Let {, , , . . . , } be an alphabet. Construct regular expressions for the following languages

i. The set of words which are zero or more repetitions of the letter .

ii. The set of words in part (i), followed by one or more repetitions of words or .

iii. The set of words in part (ii), followed by one repetition of followed by zero or more repetitions of . [6 marks]

b. Give three NFA which accept the set of words described by the three regular expressions in your answer to Question 1a (i), (ii) and (iii). [7 marks]

c. Give an example of a nondeterministic finite automaton (NFA) that is not a deterministic finite automaton (DFA). The NFA should have at least four states and be over alphabet with at least three letters. Give a brief explanation why the automaton is not a DFA. [6 marks]

d. Give three words over alphabet {, , }, which are recognised by the following regular expression: (|) (|) + () [6 marks]