Generic State Machines
The generic classes TransitionSystem, Acceptor, and Transducer provide the functionality of transition systems and finite-state machines. They rely on enumeration-type generic parameters representing the sets of states and the input and output alphabets.
StateMachines Namespace
Notes on the Generic Parameters
Delegate ValidStateTransitionAction
Delegate InvalidStateTransitionAction
NotAState and NotAnAlphabetElement Attributes
Class TransitionSystem
Public Constructor
Public Methods
ResetState
AddValidStateTransition
AddValidStateTransitionChain
AddInvalidStateTransition
IsTransitionValid
TryTransitionTo
Labyrinth
FindDeadEnds
Public Properties
CurrentState
LongestPaths
MaximumPaths
Notes
Delegate AcceptorTransitionAction
Delegate InvalidAcceptorInputHandler
Class Acceptor
Inherited Public Members
Public Constructor
Public Methods
AddStateTransitionFunctionPart
AddInvalidInput
TransitionSignal
Delegate MooreMachineOutputAction
Delegate MealyMachineOutputAction
Class Transducer
Inherited Public Members
Public Constructor
Public Methods
AddOutputFunctionPart
Signal
Examples
Room Door Example
Non-Enumeration Example
Grid Example
Zoo Example
Car Transducer Example
Compatibility and Build
Inheritance diagram:
System.Object⇽TransitionSystem⇽Acceptor⇽Transducer
The types of the namespace StateMachines depend on the generic-type parameters STATE, INPUT, and OUTPUT.
Typically, a generic-type parameter could be of any enumeration type with its enumeration members representing states.
However, it is not a strict rule. In principle, any type with public static fields can be used for the STATE type.
In this case, the public static fields will represent the transition system states.
Please see the example illustrating the use of a non-enumeration type STATE.
An instance of the delegate provides a way to define a side effect of a valid transition between two states, startState, and finishState. For example, in the hardware automation applications, it can operate the hardware.
public delegate void ValidStateTransitionAction<STATE>(STATE startState, STATE finishState);
The delegate instance is used in the TransitionSystem.AddValidStateTransition and TransitionSystem.AddValidStateTransitionChain call.
An instance of the delegate provides the optional information on an invalid transition between two states, startState and finishState. Its return string value can be used to explain why an attempted transition between the states is considered invalid.
public delegate string InvalidStateTransitionAction<STATE>(STATE startState, STATE finishState);
The delegate instance is used in the TransitionSystem.AddInvalidStateTransition call.
These attributes can be used to mark some enumeration-type members. It excludes them from the set of states or the input or output alphabets. It can be useful to create members irrelevant to the transition system behavior but used for some calculations. For example, such a member can be a bitwise OR combination of several states.
[System.AttributeUsage(System.AttributeTargets.Field, AllowMultiple = false, Inherited = false)]
public class NotAStateAttribute : ExcludeAttribute {}
[System.AttributeUsage(System.AttributeTargets.Field, AllowMultiple = false, Inherited = false)]
public class NotAnAlphabetElementAttribute : ExcludeAttribute {}
Formally, these attributes can be used interchangeably and applied to any enumeration-member public field. They are made different only for the clarity of the terms “state” and “alphabets”. The effect of these attributes is the same: the members marked with one of these attributes are skipped when building a set of states of an alphabet.
Example:
enum NotAStateAttribute {
Locked = 1, Closed = 2, Opened = 4,
OpenedInside = 8, ClosedInside = 16, LockedInside = 32,
[NotAState] Inside = OpenedInside | ClosedInside | LockedInside };
An attempt to perform a state transition to a NotAState enumeration value using TryTransitionTo will throw an exception.
The class TransitionSystem provides a way to create
a transition system based on any enumeration type
representing a set of states. For the class instance, a state transition graph can be created.
The instance can walk between states using permitted transitions,
and the optional delegate representing the side effect of a transition can be called.
An attempt to perform an invalid transition can provide optional information,
explaining why the transition is invalid.
The class also implements several graph algorithms,
including NP-hard ones,
such as finding the longest possible paths.
public class TransitionSystem<STATE> : TransitionSystemBase<STATE>{/* … */}
Creates an instance of TransitionSystem.
Parameter: STATE initialState = default. Defines the initial state of the transition system. See also ResetState.
Note that the use of a non-default initial state can be critically important when a default value
for the STATE type is not a state. It can happen if this default value is excluded using the
[NotAState] attribute. Another case of a non-state value is demonstrated by the non-enumeration example.
public TransitionSystem(STATE initialState = default);
Unconditionally jumps to the initial state defined by the constructor. No delegate instances are called even if there is a valid transition between the current state and the initial state.
public STATE ResetState();
Adds an edge to the transition system’s transition graph between the states startState and finishState. If the parameter undirected is true, it makes both transitions valid, from startState to finishState, and from finishState to startState.
Optionally, a delegate instance of the type StateTransitionAction is specified. In this case (when the delegate instance is not null), the delegate’s method will be called on each call to TryTransitionTo between corresponding states.
Note that the transition function rules are not respected by the methods Accessor.TransitionSignal and Transducer.Signal.
public void AddValidStateTransition(STATE startState, STATE finishState, StateTransitionAction<STATE> action, bool undirected = false);
Adds a transition chain to the transition system’s transition graph. Note that if the parameter undirected is true, it makes all the graph edges between the adjacent pairs of states undirected, that is, the transitions in both directions become valid.
Optionally, a delegate instance of the type StateTransitionAction is specified. In this case (when the delegate instance is not null), the same delegate’s method will be called on each call to TryTransitionTo between corresponding states in the chain.
public int AddValidStateTransitionChain(StateTransitionAction<STATE> action, bool undirected = false, params STATE[] chain)
Defines the information in an invalid state transition between the states startState and finishState. This information is used in the return of the call to IsTransitionValid and TryTransitionTo. See also InvalidStateTransitionAction.
Note that the transition function rules are not respected by the methods Accessor.TransitionSignal and Transducer.Signal.
public void AddInvalidStateTransition(STATE startState, STATE finishState, InvalidStateTransitionAction<STATE> action)
Checks if a transition between the state startState and finishState is valid. In addition to the status isValid, returns validityComment that can explain why the transition is invalid. This information is optional, defined using AddInvalidStateTransition.
public (bool isValid, string validityComment) IsTransitionValid(STATE startState, STATE finishState);
Tries to perform the transition from the current state to the state state. Returns the success status of the transition and the comment on the transition validity validityComment. If the transition is invalid, validityComment can provide some information on the reason. This information is optional, see AddInvalidStateTransition.
If the transition is successful, the current state becomes state.
An attempt to perform the transition to the same state is considered valid. In this case, no delegate methods are called.
public (bool success, string validityComment) TryTransitionTo(STATE state);
Returns all the permitted paths between the states start and finish. If shortest is true the method still finds all paths, but then it determines the shortest path length and returns only the array of paths of the minimal length.
public STATE[][] Labyrinth(STATE start, STATE finish, bool shortest = false);
Finds all “dead ends”, the states not visited along any paths between the states start and finish. Returns allPaths, all permitted paths between start and finish, and deadEnds.
public (STATE[][] allPaths, STATE[] deadEnds) FindDeadEnds(STATE start, STATE finish);
Another form of FindDeadEnds assumes that the parameter allPaths is the array of paths obtained through the prior call to Labyrinth between the state start and some other state finish. In this case, the allPaths array will contain all paths ending with the state finish passed as the second parameter to Labyrinth.
public STATE[] FindDeadEnds(STATE start, STATE[][] allPaths);
Returns the current state of the transition system. Before the very first transition of the instance, the current state is the one defined by the constructor.
public STATE CurrentState;
Finds the longest path length in the state graph. When this number is found, it finds all the possible paths with this length and returns all these paths.
public (int numberOfPaths, int longestPathLength, STATE[][] longestPaths) LongestPaths; //NP-hard
Finds the maximum number of paths between all STATE-to-STATE pairs. When this number is found, it returns the pairs having this number of paths between them.
public (int maximumNumberOfPaths, (STATE start, STATE finish)[] pairsAtMax) MaximumPaths; //NP-hard
All paths returned by Labyrinth, FindDeadEnds, and LongestPaths are represented as arrays STATE[] or arrays of paths STATE[][], each path represented as an array of STATE. In the array of states, the starting state of the path is not included, and the final state of the path is included.
In other words, given a permitted path between the current state of a transition system and the other states in the array, we can perform the chain of transitions, sequentially to all the states in the array, and all the transitions will be valid.
Example:
var solution = TransitionSystem.Labyrinth(VisitorState.Entry, VisitorState.Exit);
if (solution.Length > 0)
foreach (var state in solution[0]) // or any other solution path
TransitionSystem.TryTransitionTo(state); // always valid
The delegate AcceptorTransitionAction is used to define an acceptor’s state-transition function using AddStateTransitionFunctionPart.
public delegate STATE AcceptorTransitionAction<STATE, INPUT> (STATE state, INPUT input);
The delegate InvalidAcceptorInputHandler is used to provide additional information on invalid input using the method
AddInvalidInput.
public delegate string InvalidAcceptorInputHandler<STATE, INPUT> (STATE state, INPUT input);
The class Acceptor implements the functionality of a finite-state acceptor.
public class Acceptor<STATE, INPUT> : TransitionSystem<STATE> {/* … */}
TransitionSystem.ResetState, TransitionSystem.AddValidStateTransition, TransitionSystem.AddValidStateTransitionChain, TransitionSystem.AddInvalidStateTransition, TransitionSystem.IsTransitionValid, TransitionSystem.TryTransitionToTransitionSystem., TransitionSystem.LabyrinthTransitionSystem., TransitionSystem.FindDeadEnds, TransitionSystem.CurrentState, TransitionSystem.LongestPaths, TransitionSystem.MaximumPaths,
public Acceptor(STATE initialState = default) : base(initialState = default);
public void AddStateTransitionFunctionPart(
INPUT input, STATE state,
AcceptorTransitionAction<STATE, INPUT> handler);
The method AddInvalidInput is used to provide additional information on the state and input pair. It is used by TransitionSignal: when these methods find that a state-transition function is not implemented for a CurrentState and input pair, it looks for the invalid acceptor input information to provide an explanation of why the function is not implemented for this pair. If this additional information is not found, TransitionSignal returns a general issue description.
public void AddInvalidInput(INPUT input, STATE state, InvalidAcceptorInputHandler<STATE, INPUT> handler);
The method TransitionSignal looks at the state-transition function using the combination of input and CurrentState. If possible, it performs the transition to the state according to the state-transition function, otherwise, it reports the issues.
public record TransitionSignalResult(STATE State, bool Success, string Comment);
public TransitionSignalResult TransitionSignal(INPUT input)andler<STATE, INPUT> handler);
The delegate MooreMachineOutputAction is used to define an output function for a transducer using the Moore model,
see AddOutputFunctionPart.
public delegate OUTPUT MooreMachineOutputAction<STATE, INPUT, OUTPUT> (STATE state);
The delegate MealyMachineOutputAction is used to define an output function for a transducer using the Mealy model,
see AddOutputFunctionPart.
public delegate OUTPUT MealyMachineOutputAction<STATE, INPUT, OUTPUT> (STATE state, INPUT input);
The class Transducer implements the functionality of a finite-state transducer.
public class Transducer<STATE, INPUT, OUTPUT> : Acceptor<STATE, INPUT> {/* … */}
TransitionSystem.ResetState, TransitionSystem.AddValidStateTransition, TransitionSystem.AddValidStateTransitionChain, TransitionSystem.AddInvalidStateTransition, TransitionSystem.IsTransitionValid, TransitionSystem.TryTransitionToTransitionSystem., TransitionSystem.LabyrinthTransitionSystem., TransitionSystem.FindDeadEnds, TransitionSystem.CurrentState, TransitionSystem.LongestPaths, TransitionSystem.MaximumPaths,
Accessor.AddStateTransitionFunctionPart, Accessor.AddInvalidInput, Accessor.TransitionSignal
public Transducer(STATE initialState = default) : base(initialState);
There are two functions under the same name AddOutputFunctionPart: one is used to develop a Moore finite-state machine, and another one — to develop a Mealy finite-state machine.
Moore version:
public void AddOutputFunctionPart(
INPUT input, STATE state,
MooreMachineOutputAction<STATE, INPUT, OUTPUT> handler);
Mealy version:
public void AddOutputFunctionPart(
INPUT input, STATE state,
MealyMachineOutputAction<STATE, INPUT, OUTPUT> handler);
If an output function of a state machine uses a mixture of Moore and Mealy functions for different function arguments, it is, formally speaking, a Mealy machine.
See also: MooreMachineOutputAction, MealyMachineOutputAction.
The method Signal looks for both state-transition function and output function using the combination of input and Acceptor.CurrentState. If possible, it performs the transition to the state according to the state-transition function and calculates the Output, otherwise, it reports the issues.
In other words, it calls Acceptor.TransitionSignal, takes its output, then uses the output function, and combines the results.
public record SignalResult(
TransitionSignalResult TransitionResult,
OUTPUT Output, bool OutputSuccess = true, string OutputComment = null);
public SignalResult Signal(INPUT input);
Basic transition system example with 6 states forming a linear transition graph. Demonstrates valid transitions and attempts to perform an invalid transition.
This example shows the use of a non-enumerable type as a TransitionSystem generic parameter. The type double is used as a source of the state set.
This example demonstrates that NP-hard problems can be pretty hard even for the 24 states. The states in this example form a 6x4 grid with the permitted undirected transition between all neighboring cells. The example demonstrates the calculation of the longest path between two states and the maximum number of possible paths.
Maximum number of paths between a pair of states is 5493.
Total number of paths: 1603536, longest path length: 23.
The Zoo example demonstrates the transition system representing the visitor location at the zoo. This example demonstrates all the TransitionSystem features.
The Car Transducer Example is a comprehensive example demonstrating Acceptor and Transducer features on a highly simplified model of a car with automatic transmission, keyless entry, only three gearbox positions, and lights.
The solution is compatible with any .NET version. For the earliest common denominator, I use v. 5; by the moment of writing, I tested the versions from 5 to 9.
To change the target .NET version, edit the file “Directory.Build.props”, the property <TargetFramework>.
Also, the code can be used for some .NET Framework versions. However, it will require re-creation of project files, which is not hard to do.
The build does not require Visual Studio, Visual Studio Code, or any other IDE. It can be done using the commands
dotnet build -c Debug dotnet build -c Release
With Visual Studio or Visual Studio Code, the code can be built in the usual ways. Besides, for Visual Studio Code, a launch configuration “Build All” and a task “Build All” are provided.
This documentation is generated from the extended Markdown documentation using Extensible Markdown for Visual Studio Code.