NLP.GenI.Automaton
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
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
 data NFA st ab Source
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 :: NFA st ab -> [st] Source
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 :: (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 dead-end.

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
 numStates :: NFA st ab -> Int Source
 numTransitions :: NFA st ab -> Int Source