Data.DFA

Representation of DFAs and some simple algorithms on them.

Documentation

data DFA

The type of DFAs is abstract: it is a pointer to a C struct.

type Label = CUInt

Labels are represented using C unsigned ints.

type State = CUInt

States are represented using C unsigned ints.

Initialisation

initialize :: IO DFA

Create a new DFA.

finished :: DFA -> IO ()

Garbage-collect a DFA.

Construction

addInitialTransition :: DFA -> (Label, State) -> IO ()

Add an initial transition for the given Label to the given State to DFA.

addTransition :: DFA -> (State, Label, State) -> IO ()

Add a transition from the given State on the given Label to the given State to DFA.

setSatBit :: DFA -> State -> IO ()

Set the bit associated with State. Used to indicate finality, acceptance, etc. The minimization algorithm will distinguish states with different bits (that are otherwise bisimilar).

minimize :: DFA -> IO ()

Reduce the DFA using Hopcroft's algorithm.

Traversal

foldInitialTransitions :: DFA -> ((Label, State, Bool) -> b -> IO b) -> b -> IO b

Traverse the initial transitions of DFA by invoking the given function on each of them.

DFAs aren't functorial (they're monomorphic), so we cannot use Traversable.

foldTransitions :: DFA -> ((State, Label, State, Bool) -> b -> IO b) -> b -> IO b

Traverse the transitions of DFA by invoking the given function on each of them.

DFAs aren't functorial (they're monomorphic), so we cannot use Traversable.

Inspection

numStates :: DFA -> IO CUInt

Returns the number of states that are actually present in DFA.

numSymbols :: DFA -> IO CUInt

Returns the number of symbols that are actually present in DFA.

writeDotToFile :: DFA -> FilePath -> (Label -> String) -> IO ()

Write DFA to a file with the given FilePath, using the given labelling function.