Safe Haskell	Safe-Infered

Data.DFA

Contents

Initialisation
Construction
Traversal
Inspection

Description

Representation of DFAs and some simple algorithms on them.

Synopsis

Documentation

data DFA Source

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

type Label = CUInt Source

Labels are represented using C unsigned ints.

type State = CUInt Source

States are represented using C unsigned ints.

Initialisation

initialize Source

Arguments

:: Bool	Debugging?
-> State	Initial state
-> IO DFA

Create a new DFA.

finished :: DFA -> IO ()Source

Garbage collect a DFA.

Construction

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

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

setFinal :: DFA -> State -> IO ()Source

Set the final bit associated with State.

The minimization algorithm will distinguish states with different bits (that are otherwise bisimilar).

minimize Source

Arguments

:: DFA
-> Bool	Preserve states that cannot reach final states.
-> IO ()

Reduce the DFA using Antti Valmari's algorithm. The result should be the same as for the standard algorithm due to Hopcroft.

Traversal

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

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

getInitialState :: DFA -> IO State Source

Get the initial state.

numStates :: DFA -> IO CUInt Source

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

numSymbols :: DFA -> IO CUInt Source

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

isFinal :: DFA -> State -> IO Bool Source

Is the state s final?

debugging :: DFA -> IO Bool Source

Is the debugging flag set?

loadFromFile :: FilePath -> IO DFA Source

Load a DFA from a file in a standard format. (See the accompanying examples and dfa.c for details.)

dumpToFile :: DFA -> FilePath -> IO ()Source

Dump a DFA to a file in a standard format. (See the accompanying examples and dfa.c for details.)