fsmActions-0.1: Finite state machines and FSM actions




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.


Data types

type State = IntSource

States are integers, counting from zero.

newtype DestinationSet Source

Destination sets are just lists of States.




destinations :: [State]

newtype Action Source

Actions are lists of DestinationSets, indexed by source State.




newtype FSM sy Source

Finite state machine whose nodes are labelled with type sy.




unFSM :: Map sy Action


Eq sy => Eq (FSM sy) 
Ord sy => Ord (FSM sy) 
Show sy => Show (FSM sy) 

newtype Word sy Source

Words are lists of symbols.


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 ActionSource

Look up a symbol's Action in an FSM


data WellFormed sy Source

An FSM is well-formed if all its actions are the same length, and none of its actions contain destinations which are out of range.


WellFormed [sy]

FSM is well-formed. (Carries an empty list: this is a slight wart, as no cargo is necessary; unfortunately, fixing that would require use of a GADT here, which seems excessive.)

BadLengths [(sy, Int)]

Lengths of Actions in the FSM don't all match. Carries a sorted list of (symbol, Action length) pairs, one for every symbol in the alphabet of the FSM.

BadActions [(sy, Action)]

Some Actions contain out-of-range (negative or too-high) destinations. Carries a sorted list of all such actions and their corresponding symbols.


Eq sy => Eq (WellFormed sy) 
Show sy => Show (WellFormed sy) 

isWellFormed :: Ord sy => FSM sy -> WellFormed sySource

Check if an FSM is well-formed or not.


normalise :: FSM sy -> FSM sySource

Normalise an FSM, i.e. normalise all its Actions.

Operations on actions

mkAction :: [[State]] -> ActionSource

Build an action given a nested list of destination states.

mkDAction :: [State] -> ActionSource

Build a deterministic action given a list of destination states.

append :: Action -> Action -> ActionSource

Append two Actions, ie compute the Action corresponding to the application of the first followed by the second.

actionLookup :: Action -> State -> DestinationSetSource

Compute the DestinationSet reached by following some Action from some State.

action :: Ord sy => FSM sy -> Word sy -> Maybe ActionSource

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

Test if two Words are action-equivalent over some FSM.

Destination sets

destinationSet :: Ord sy => FSM sy -> State -> Word sy -> Maybe DestinationSetSource

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

Test if two Words are destination-equivalent at some State of an FSM.


fsmIdentity :: FSM sy -> ActionSource

Compute the identity action for a given FSM.


isDAction :: Action -> BoolSource

Test if an Action is deterministic or not.

isDFSM :: FSM sy -> BoolSource

Compute whether an FSM is deterministic or not.