GenI-0.23.20130212: A natural language generator (specifically, an FB-LTAG surface realiser)

Safe HaskellSafe-Infered



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.



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




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



:: (Ord ab, Ord st) 
=> NFA st ab 
-> st

from state

-> Maybe ab


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