Data.FsmActions
 Contents Data types Simple FSM operations Normalisation Operations on actions Destination sets Identity Determinism
Description

Finite state machines.

Here an FSM is a map from symbols to actions. Symbols are parametric (will usually be Strings or Chars). Actions specify the action of a symbol on each state, and are represented as lists of transitions: one per state. States are just numbers, from 0 to n, corresponding to indices on transition lists in Actions. Then deterministic actions are just Ints, identifying the state to transition to under that action; nondeterministic actions are lists of Ints: all the states to possibly transition to under that action.

Synopsis
type State = Int
newtype DestinationSet = DestinationSet {
 destinations :: [State]
}
newtype Action = Action {
 destinationSets :: [DestinationSet]
}
newtype FSM sy = FSM {
 unFSM :: Map sy Action
}
newtype Word sy = Word [sy]
states :: FSM sy -> [State]
alphabet :: FSM sy -> [sy]
fsmAction :: Ord sy => sy -> FSM sy -> Maybe Action
normalise :: FSM sy -> FSM sy
normaliseAction :: Action -> Action
mkAction :: [[State]] -> Action
mkDAction :: [State] -> Action
append :: Action -> Action -> Action
actionLookup :: Action -> State -> DestinationSet
action :: Ord sy => FSM sy -> Word sy -> Maybe Action
actionEquiv :: Ord sy => FSM sy -> Word sy -> Word sy -> Bool
destinationSet :: Ord sy => FSM sy -> State -> Word sy -> Maybe DestinationSet
destinationEquiv :: Ord sy => FSM sy -> State -> Word sy -> Word sy -> Bool
fsmIdentity :: FSM sy -> Action
identity :: Int -> Action
isDAction :: Action -> Bool
isDFSM :: FSM sy -> Bool
Data types
 type State = Int Source
States are integers, counting from zero.
 newtype DestinationSet Source
Destination sets are just lists of States.
Constructors
DestinationSet
 destinations :: [State]
Instances
 Eq DestinationSet Ord DestinationSet Show DestinationSet
 newtype Action Source
Actions are lists of DestinationSets, indexed by source State.
Constructors
Action
 destinationSets :: [DestinationSet]
Instances
 Eq Action Ord Action Show Action
 newtype FSM sy Source
Finite state machine whose nodes are labelled with type sy.
Constructors
FSM
 unFSM :: Map sy Action
Instances
 Eq sy => Eq (FSM sy) Ord sy => Ord (FSM sy) Show sy => Show (FSM sy)
 newtype Word sy Source
Words are lists of symbols.
Constructors
 Word [sy]
Simple FSM operations
 states :: FSM sy -> [State] Source
Compute the list of states of the FSM. Only really meaningful if the FSM's well-formedness is not BadLengths. With current implementation, is just [0..n] for some n (or empty).
 alphabet :: FSM sy -> [sy] Source
Compute the alphabet of an FSM.
 fsmAction :: Ord sy => sy -> FSM sy -> Maybe Action Source
Look up a symbol's Action in an FSM
Normalisation
 normalise :: FSM sy -> FSM sy Source
Normalise an FSM, i.e. normalise all its Actions.
 normaliseAction :: Action -> Action Source
Operations on actions
 mkAction :: [[State]] -> Action Source
Build an action given a nested list of destination states.
 mkDAction :: [State] -> Action Source
Build a deterministic action given a list of destination states.
 append :: Action -> Action -> Action Source
Append two Actions, ie compute the Action corresponding to the application of the first followed by the second.
 actionLookup :: Action -> State -> DestinationSet Source
Compute the DestinationSet reached by following some Action from some State.
 action :: Ord sy => FSM sy -> Word sy -> Maybe Action Source
Compute the Action for some Word over some FSM. The word might contain symbols outside the FSM's alphabet, so the result could be Nothing.
 actionEquiv :: Ord sy => FSM sy -> Word sy -> Word sy -> Bool Source
Test if two Words are action-equivalent over some FSM.
Destination sets
 destinationSet :: Ord sy => FSM sy -> State -> Word sy -> Maybe DestinationSet Source
Compute the DestinationSet for some Word at some State of an FSM. The word might contain symbols outside the FSM's alphabet, or the state might be out of range, so the result could be Nothing.
 destinationEquiv :: Ord sy => FSM sy -> State -> Word sy -> Word sy -> Bool Source
Test if two Words are destination-equivalent at some State of an FSM.
Identity
 fsmIdentity :: FSM sy -> Action Source
Compute the identity action for a given FSM.
 identity :: Int -> Action Source
Compute the identity action for a given number of states
Determinism
 isDAction :: Action -> Bool Source
Test if an Action is deterministic or not.
 isDFSM :: FSM sy -> Bool Source
Compute whether an FSM is deterministic or not.