Safe Haskell | None |
---|---|

Language | Haskell2010 |

# Types

Non-Deterministic Finite State Automaton.

Some notes on the implementation and design:

- You can transition to any non-negative number of states (including 0).
- There is only one start state.
- We use the Thompson encoding. This means that there is an epsilon transition that consumes no input.
- We store the full epsilon closure for every state. This means that, when evaluating the NFA, we do not ever need to compute the closure.
- There is no Eq instance for NFA. In general, this can take exponential time. If you really need to do this, convert the NFA to a DFA.

Invariants:

- The start state is always the state at position 0.
- The length of nfaTransition is given by nfaStates.

# Conversion

toDfsa :: (Ord t, Bounded t, Enum t) => Nfsa t -> Dfsa t Source #

Convert an NFSA to a DFSA. For certain inputs, this causes the number of states to blow up expontentially, so do not call this on untrusted input.