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

^{n}, 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

_{0},F) then the equivalent DFA will be M'(Q',S,d',q_{0}',F'):- Q' is the set of all subsets of Q. That is the power set of Q
- S stays the same
- q
_{0}' will represent the starting position of the NFA. When M starts processing the word, the only active state is the initial state q_{0}. Then q_{0}' = {q_{0}} - 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.

## No comments:

## Post a Comment