NLP.GenI.Automaton

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.

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