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

newtype FSM sy Source

Finite state machine whose nodes are labelled with type sy.

Constructors

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

Well-formedness

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.

Constructors

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 `Action`s contain out-of-range (negative or too-high) destinations. Carries a sorted list of all such actions and their corresponding symbols.

Instances

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.

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.

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.