# Regular Expressions and Finite Automata

#### Difficulty: ***

The specification for this exercise is quite long, so we gave students a short introductory document to read the night before the test.  Most students did very well in Parts I and II, but were then slowed down by Part III.  Common errors were in the state labelling and/or the chaining of the state identifiers into and out of the make function.  Quite a number of students had a go at Part IV, which is hard to get your head around in the time available.  Amazingly, one student completed the entire exercise in just over two hours, scoring 100%, so it could be done.

I have made one small adjustment to the original structure by including the labels function in Part II.  A number of students who attempted Part IV made heavy weather of groupTransitions, which should be a one-liner.  The labels function, simple though it is, might help.

The acceptance testing algorithm used here is the simple backtracking version.  However, if you implement getFrontier correctly from Part IV then you’ll find that it’s relatively straightforward to use it to build the breadth-first version of acceptance testing which is substantially more efficient (see below).

Remark: Most treatments of NFA to DFA conversion are based on the calculation of the so-called $\epsilon$-closure of a set of states. The trouble with this is that it introduces superfluous states in the resulting DFA. These are avoided by using the $\epsilon$-frontier instead, as described in the specification. Does the use of frontiers yield the minimal DFA? Sadly not.