|
|
|
| Description |
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.
1. 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.
2. We model the empty an empty transition as the transition on
Nothing. All other transitions are Just something.
|
|
| Synopsis |
|
|
|
| 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
| | Constructors | | NFA | | | startSt :: st | | | isFinalSt :: Maybe (st -> Bool) | finalSt will use this if defined
| | finalStList :: [st] | can be ignored if isFinalSt is defined
| | transitions :: Map st (Map st [Maybe ab]) | there can be more than one transition between any two states
and a transition could be the empty symbol
| | states :: [[st]] | if you don't care about grouping states into columns
you can just dump everything in one big list
|
|
|
|
|
|
| finalSt returns all the final states of an automaton
|
|
|
| :: (Ord ab, Ord st) | | | => NFA st ab | from state
| | -> st | transition
| | -> Maybe ab | to state
| | -> st | | | -> NFA st ab | |
|
|
|
| lookupTrans aut st1 ab returns the states that st1 transitions
to via a.
|
|
|
Returns all possible paths through an automaton from the
start state to any dead-end.
Each path is represented as a list of labels.
We assume that the automaton does not have any loops
in it.
|
|
|
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
|
|
|
|
|
|
| Produced by Haddock version 2.6.0 |
