Safe Haskell	Safe-Infered

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.

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 are Just something.

Synopsis

Documentation

data NFA st ab

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

Fields

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]

finalSt returns all the final states of an automaton

addTrans

Arguments

:: (Ord ab, Ord st)
=> NFA st ab
-> st	from state
-> Maybe ab	transition
-> st	to state
-> NFA st ab

lookupTrans :: (Ord ab, Ord st) => NFA st ab -> st -> Maybe ab -> [st]

lookupTrans aut st1 ab returns the states that st1 transitions to via a.

automatonPaths :: (Ord st, Ord ab) => NFA st ab -> [[ab]]

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]]]

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

numTransitions :: NFA st ab -> Int