## Friday, 12 November 2010

### Turning NFAs into DFAs

The first bit we are going to write is concerned with converting the NFA into a DFA. I am not going to prove that the two are actually equivalent, I'll only show the construction of the DFA. The idea here is that any NFA can be simulated by a DFA with an exponentially increased number of states. Think about it, when the NFA starts consuming the word it's been fed at each step it maintains active a number of sets. Upon consuming each letter, the set of active states changes according to the transition function:

If A is the set of active states at one point then, after one step the set of active positions will be:

We can simulate this by constructing a DFA which represents every possible combination of active NFA states. Then the number of states will be at least 2n, as any subset of the set of states in the NFA has to be represented.

The DFA transition rule will be the transition from A to A' shown above.

Let's express this formally so we'll be able to convert it to Haskell easily. If the NFA is M(Q,S,d,q0,F) then the equivalent DFA will be M'(Q',S,d',q0',F'):

Converting this to Haskell code will be fairly easy, baring some concerns about types. Before we get started on that, let us take a look at a DFS search on a graph in Haskell.