Data.FsmActions

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

States are integers, counting from zero.

newtype DestinationSet

Destination sets are just lists of States.

Constructors

DestinationSet

Fields

destinations :: [State]

Instances

Eq DestinationSet

Ord DestinationSet

Show DestinationSet

newtype Action

Actions are lists of DestinationSets, indexed by source State.

Constructors

Action

Fields

destinationSets :: [DestinationSet]

Instances

Eq Action

Ord Action

Show Action

data FSM sy

Finite state machine whose nodes are labelled with type sy.

Instances

Eq sy => Eq (FSM sy)

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

Show sy => Show (FSM sy)

newtype Word sy

Words are lists of symbols.

Constructors

Word [sy]

Simple FSM operations

fromList :: Ord sy => [(sy, Action)] -> FSM sy

Create an FSM from a list of symbol, Action pairs.

toList :: FSM sy -> [(sy, Action)]

Turn an FSM into a list of symbol, Action pairs.

delete :: Ord sy => sy -> FSM sy -> FSM sy

Delete a symbol and its action from an FSM.

lookup :: Ord sy => sy -> FSM sy -> Maybe Action

Look up a symbol's Action in an FSM

fsmMap :: (sy -> Action -> a) -> FSM sy -> [a]

Map a function over the FSM.

states :: FSM sy -> [State]

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]

Compute the alphabet of an FSM.

Normalisation

normalise :: FSM sy -> FSM sy

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

normaliseAction :: Action -> Action

Operations on actions

mkAction :: [[State]] -> Action

Build an action given a nested list of destination states.

mkDAction :: [State] -> Action

Build a deterministic action given a list of destination states.

append :: Action -> Action -> Action

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

actionLookup :: Action -> State -> DestinationSet

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

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

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

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

Destination sets

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

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

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

Identity

fsmIdentity :: FSM sy -> Action

Compute the identity action for a given FSM.

identity :: Int -> Action

Compute the identity action for a given number of states

Determinism

isDAction :: Action -> Bool

Test if an Action is deterministic or not.

isDFSM :: FSM sy -> Bool

Compute whether an FSM is deterministic or not.