Section 11.2 State Machine in SageMath
Although SageMath does have a dedicated built-in module to handle state machines, we can still model, construct, display, and run relatively simple state machines, leveraging the general-purpose tools, such as graphs and transition matrices, to represent and work with state machines.
In this section, we’ll explore how to define states, create a state transition graph, visualize the state machine, and simulate its execution in SageMath.
Subsection 11.2.1 Define States, Transitions and Outputs
The first step is to define the states and transitions in the state machine. We can represent these using lists and dictionaries.
The states are defined as vertices in the graph, the transitions (along with the outputs) are defined as directed edges between these vertices.
Subsection 11.2.2 Create Graph Model of State Machine
In SageMath, we can use the
DiGraph class to represent the states, transitions and outputs of the state machine as a directed graph, and use the graph structure to visualize the state machine representation.Subsection 11.2.3 Display the State Machine
The
SM.show() command renders a graphical representation of the state machine. Each vertex in the graph represents a state, and each directed edge represents a transition, labeled with the input.Subsection 11.2.4 Run the State Machine
Next, we can simulate the state machine’s behavior by creating a function that processes a list of inputs and transitions through the states accordingly.
The
run_state_machine function simulates the state machine by processing a list of inputs starting from an initial state.Subsection 11.2.5 Using Sage built-in ’FiniteStateMachine’
FiniteStateMachine() is used define an empty state machine.FSMState() helps define state for the given label, the is_initial flag can be set to true to indicate the current state will be the initial state of the finite state machine. add_state() method is then used to append the state to the state machineTo check whether or not a finite state machine has a state defined,
has_state() method can be used by passing in the state label (case-sensitive).states() method is used to enumerate the list of all defined states of the state machine.initial_states() method lists the defined initial state(s) of the state machine.FSMTransition() defines a new transition between two states, as well as the input (the transition trigger) and output associated with the new state after teh transition.add_transition() method attach the defined transition to the state machine. transitions() method is used to enumerate the list of all defined transitions of the state machine.Once the states and transitions as defined, the state machine can berun using
process() method.process() method also returned the list of intermediary outputs during the state machine run.graph() command displays the graph representation of the state machine.The
FiniteStateMachine class also offers LATEX representation of the state machine using the latex_options() method.The above are basic commands with a typical workflow of defining and running of simple finite state machines. The general structure of the state machine can be adapted to fit different use cases. The examples shown can be customized and fine-tuned to reflect more complex scenarios (more states, different input sequences, ...etc).
