Designing State Machines using Python [A Quick Guide]

Desigining State Machines Using Python

Hello there! In this article, we will study some of the basics of Computer Science. Not the entire course, of course! Just a part of the Theory of Computation. This subject is about the design of Finite Automata. We will discuss all the terms in the further part. So, let us do it.

What is a state machine in Python?

A state machine is a behavioral model that defines how an object behaves in response to events. In Python, a state machine is typically implemented as a finite state machine (FSM). An FSM is a mathematical model of computation that can be used to design digital logic circuits and computer programs. It consists of a set of states, transitions between those states, and actions that are performed when a transition occurs.

A finite state machine (FSM) is a mathematical model of computation that can be used to design digital logic circuits and computer programs. It consists of a set of states, transitions between those states, and actions that are performed when a transition occurs. An FSM can be represented as a directed graph, with the states represented as nodes and the transitions represented as edges. The edges are labeled with the events that trigger the transition, and the actions are associated with the edges.

What is TOC and Automata?

Automata theory and TOC are both used to study the behavior of machines, but they take different approaches. Automata theory focuses on the abstract machine itself, while TOC looks at the problems that can be solved using that machine.

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. Automata theory is also closely related to formal language theory, as the automata are often used as models of computation for formal languages. Theory of Computation (TOC) is a branch of mathematics that deals with the study of algorithms and their efficiency. It is concerned with the design and analysis of algorithms, data structures, and complexity theory.

The Theory of Computation is a topic in which we design some virtual machines that work upon basic input and output. From the very root level, working starts from accepting strings of definite lengths. The basic nomenclature of these machines is Automata.

There are two types of automata:

  1. Deterministic Finite Automata (DFA).
  2. Non-Deterministic Finite Automata (NDFA).

Understanding of Deterministic Finite Automata (DFA)

A deterministic finite automaton (DFA) is a special type of finite state machine that accepts or rejects a string of symbols, called an input string, based on a deterministic algorithm. A DFA can be represented as a directed graph, with the states represented as nodes and the transitions represented as edges. The edges are labeled with the events that trigger the transition, and the actions are associated with the edges.

Understanding Non-Deterministic Finite Automata (NDFA)

A nondeterministic finite automaton (NDFA) is a special type of finite state machine that can accept or reject an input string based on a non-deterministic algorithm. An NDFA can be represented as a directed graph, with the states represented as nodes and the transitions represented as edges. The edges are labeled with the events that trigger the transition, and the actions are associated with the edges.

A basic automaton is a tuple of five units:

Automata = (Q, F, δ, q0, Σ)
  1. Q = A set of all states.
  2. F = Set of all final states.
  3. δ = The transition function or mapping function that maps the movement of states with each input.
  4. q0 = The initial state.
  5. Σ = A finite set of input symbols.

The diagram of a basic DFA

Automata Diagram
Automata diagram

This machine accepts the string “aa”. The diagram here is the most simple representation of a DFA. Let us understand its parameters:

  1. Here Q = {q0, q1, q2}. A set of final states.
  2. q0 is the initial state.
  3. q2 is the final state
  4. Σ = {a} is the set of all input symbols.

This machine consists of three states – q0, q1, and q2. Initially, when we give input to a state it transits/moves to another state. The transition function (δ) keeps a track of all these activities. And when the desired string reaches a particular state, we define it as the final state of that machine.

Applications of Automata

Automata theory is the study of abstract machines and the computational problems that can be solved using them. Automata are used in a variety of applications, including verification, model checking, scheduling, and database updates. Here are 3 applications of Automata

  1. Game development
  2. Artificial Intelligence
  3. Compiler Design

Let’s now jump to building a state machine using Python’s statemachine library.

Building a state machine using Python

We are going to program our own State Machine using Python. This will be the same as drawing it on Paper. Also we will be checking the transitions using some special operations.

1. Installing the statemachine library

Open your command prompt and type the pip command:

pip install python-statemachine
Installing Python Statemachine
Installing Python Statemachine

Tools and technologies

  1. Python version: 3.8.x or above.
  2. Supportive library: python-statemachine.
  3. A good IDE: VSCode, Spyder, etc.

Code:

from statemachine import StateMachine, State

class LightBulb(StateMachine):

    # creating states
    offState = State("off", initial = True)
    onState = State("on")
     
    # transitions of the state
    switchOn = offState.to(onState)
    switchOff = onState.to(offState)
    
        
bulb = LightBulb()
print(bulb.current_state)

Output:

State('off', identifier='offState', value='offState', initial=True)

Explanation:

  1. We first import the state machine module along with the State class.
  2. We first create a class LightBulb. Then, to inherit the properties give the StateMachine inside the parenthesis.
  3. We create two states.
    1. offState: to denote that initially, the bulb is off. Setting up the initial parameter to True.
    2. onState: to switch on the bulb.
  4. Then, create two transitions:
    1. switchOn: To transit from offState to onState.
    2. switchOff: To transit from onState to offState.
  5. Create an instance of our class namely bulb.
  6. Then to check the current state we simply call the current_state attribute of the bulb object.
  7. We see that the current state of the bulb is “off”.

Dynamic properties of State Machines

When we create a State Machine the module creates a special set of properties for each state present in that machine. We can check whether that property is working for that state or not using the instance and the property. In the above code, we have two such states. So, the properties created are also True.

Code to check the property:

bulb.is_offState # returns True
bulb.is_onState # returns False

Checking the number of states and transitions

Let’s look at how we can pull the transitions and all the states from a State class. This may not look useful when our class only has two states. But consider classes with multiple possible states and that’s when these techniques will be handy.

Code to check the number of states:

In automata, we need to keep a record of all the current states. To do this we use the following list comprehension.

a = [s.identifier for s in bulb.states]
print(a)

Output:

['offState', 'onState']

Explanation:

  1. We use the list comprehensions to store all the states in a list.
  2. Then using the “identifier” attribute, run a for a loop.
  3. Fetch each state using the states attribute. We need to call it using the bulb object which is the instance of our LightBulb class.
  4. Assign this list to a variable “a”.
  5. Then print it. We get all the states.

Code to check the transitions:

Automata always transit from one state to another state. In simple words, we call it transition. So, to record them, our StateMachine has, we have the transitions attribute.

b = [s.identifier for s in bulb.transitions]
print(b)

Output:

['switchOff', 'switchOn']

Explanation:

All the code remains the same as that of states. We just use the “transitions” keyword with the bulb object.

Conclusion

So, in this way, we can build a simple state machine using Python. These machines are one of the important concepts to study when we are designing an AI algorithm or a game. For the logic building also State MAchines good on-page topics. So, here we conclude this topic.

Reference

You can check more on these by visiting this link: https://pypi.org/project/python-statemachine/