Data.FsmActions

Contents

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

Data types

type State = Int Source

States are integers, counting from zero.

newtype DestinationSet Source

Destination sets are just lists of States.

Constructors

DestinationSet
Fields destinations :: [State]

Instances

Eq DestinationSet
Ord DestinationSet
Show DestinationSet

newtype Action Source

Actions are lists of DestinationSets, indexed by source State.

Constructors

Action
Fields destinationSets :: [DestinationSet]

Instances

Eq Action
Ord Action
Show Action

data FSM sy Source

Finite state machine whose nodes are labelled with type sy.

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

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

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

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

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

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

Delete a symbol and its action from an FSM.

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

Look up a symbol's Action in an FSM

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

Map a function over the FSM.

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.

Normalisation

normalise :: FSM sy -> FSM sySource

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.