Turning NFAs into DFAs

See previous post. | See next post

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 2ⁿ, 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,q₀,F) then the equivalent DFA will be M'(Q',S,d',q₀',F'):

• Q' is the set of all subsets of Q. That is the power set of Q
• S stays the same
• d' tells us where we can go from a state given a symbol. Then:
  

  

  Where q -> p means there exists a transition from q to p that involves only the symbol s and possibly some epsilon transitions.
  Note that this acts on sets of states from the NFA. This will prove to be a slight hindrance later on.
• q₀' will represent the starting position of the NFA. When M starts processing the word, the only active state is the initial state q₀. Then q₀' = {q₀}
• F' requires a bit of thought. When do we consider a word accepted by the NFA? When there is a path we can take through M such that we end up in an accepting state. However, our DFA keeps track of all the active states. Then, to consider a state as an accepting one in the DFA it must only accept words that are accepted in the NFA a well. So they must contain an accepting state of the NFA. Then:
  
  

  

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.