Safe Haskell  None 

This module provides a simple, naive implementation of nondeterministic finite automata (NFA).
The transition function consists of a Map
, but there are also accessor
function which help you query the automaton without worrying about how
it's implemented.
 The states are a list of lists, not just a simple flat list as you might expect. This allows you to optionally group your states into "columns" which is something we use in the GenI polarity automaton optimisation.
 We model the empty an empty transition as the transition on
Nothing
. All other transitions areJust
something.
 data NFA st ab = NFA {
 startSt :: st
 isFinalSt :: Maybe (st > Bool)
 finalStList :: [st]
 transitions :: Map st (Map st [Maybe ab])
 states :: [[st]]
 finalSt :: NFA st ab > [st]
 addTrans :: (Ord ab, Ord st) => NFA st ab > st > Maybe ab > st > NFA st ab
 lookupTrans :: (Ord ab, Ord st) => NFA st ab > st > Maybe ab > [st]
 automatonPaths :: (Ord st, Ord ab) => NFA st ab > [[ab]]
 automatonPathSets :: (Ord st, Ord ab) => NFA st ab > [[[ab]]]
 numStates :: NFA st ab > Int
 numTransitions :: NFA st ab > Int
Documentation
Note: you can define the final state either by setting isFinalSt
to Just f
where f
is some function or by putting them in
finalStList
NFA  

lookupTrans :: (Ord ab, Ord st) => NFA st ab > st > Maybe ab > [st]Source
lookupTrans
aut st1 ab
returns the states that st1
transitions
to via a
.
automatonPaths :: (Ord st, Ord ab) => NFA st ab > [[ab]]Source
Returns all possible paths through an automaton from the start state to any deadend.
Each path is represented as a list of labels.
We assume that the automaton does not have any loops in it.
automatonPathSets :: (Ord st, Ord ab) => NFA st ab > [[[ab]]]Source
The set of all bundled paths. A bundled path is a sequence of states through the automaton from the start state to any dead end. Any two neighbouring states can have more than one possible transition between them, so the bundles can multiply out to a lot of different possible paths.
The output is a list of lists of lists:
 Each item in the outer list is a bundled path through the automaton, i.e. without distinguishing between the possible transitions from any two neighbouring states
 Each item in the middle list is represents the set of transitions between two given neighbouring states
 Each item in the inner list represents a transition between two given states
numTransitions :: NFA st ab > IntSource