Automata Theory in Python 🐍: (Part 1) Deterministic Finite Automata

Published in

The Startup

7 min readJun 6, 2020

Why are you trying to implement Automata Theory in Python?

During my time as a sophomore Computer Science major, I paid more attention to practical subjects like Object Oriented Programming than theoretical subjects like Principles of Programming Languages. I adored any subject that focused on coding solutions to assignments than studying walls of dry text. But that came to change when I attended Theory of Computation during junior year of college. I started to appreciate theory and learned how vital it is to numerous areas of programming including compilers and artificial intelligence.

I wanted to practice my Python by implementing something that was both interesting and theoretical. Automata Theory easily fit the bill. In this article, we will achieve the following objectives:

Learn what is Automata Theory.
Learn about Finite State Machines (FSM) and more specifically Deterministic Finite Automata (DFA).
Learn how to implement DFA in Python using Object Oriented Programming (OOP).

What is Automata Theory?

Automata Theory is a branch of theoretical computer science that deals with abstract machines and automata. An automaton is a construct that runs by itself (based on predetermined instructions) when an input is given. It is defined by a number of properties. It consists of states and transitions between states. Depending on the input, the current state changes to the next state. This change of state based on input is a predefined instruction and is stored in a construct called the Transition Function. The input is parsed using the Transition Function, that is usually in the form of a table. Depending on the final state, the input is ACCEPTED or REJECTED. The goal state is called the Accept State and all other states are called the Reject States.

The above terminology might seem confusing. Let’s explore it by asking a common question: How do I give my math exam? We can illustrate the steps of this problem by the use of a Transition Diagram:

Transition Diagram of automata that shows how to write your math exam. — Figure 1 : Example of a Transition Diagram

So, before you give your math exam, you receive the syllabus for the test. We can then read the syllabus to understand what’s going to be on the test. After reading the syllabus, we can re-read it as many times as we want, but we won’t make any progress unless we study the syllabus. After we study the syllabus, we can practice till we are better at tackling the content. After practicing, we can give our exam which leads us to our end goal. We know where to go based on the transition table. For example, ‘Syllabus Known (Q1)’ on ‘Read Syllabus’ will lead us to the same state Q1. If we ‘Study Syllabus’ we go to the next state ‘Studied Syllabus (Q2)’. One possible input sequence that will lead us to the accept state is READ SYLLABUS -> STUDY SYLLABUS -> STUDY SYLLABUS -> GIVE TEST. Another valid sequence to reach the input sequence is READ SYLLABUS -> READ SYLLABUS -> STUDY SYLLABUS -> GIVE TEST. However, the following sequence will not lead us to an accepting state: READ SYLLABUS -> STUDY SYLLABUS. This is because you haven’t given the test which is our end goal in this example. The accept state is therefore Q3 and the others are reject states. All input is parsed from state Q0 which is our start state. The input alphabet can be described as the set of phrases {READ SYLLABUS, STUDY SYLLABUS, GIVE TEST}. The transition function is a mapping of (state, input alphabet)->(state). Hopefully, you can see how many problems, situations and games can be depicted using automata and understand it’s significance.

Types of automata. — Figure 2 : Types of automata (top-half) and their corresponding Chomsky Hierarchy of Languages (bottom-half) [Image Source]

Automata can be divided into a number of categories. We will get into detail about each type in subsequent articles. In this article, we will specifically talk about Finite State Machines/Automata (FSM/FSA) like Deterministic Finite Automata (DFA), Non-deterministic Finite Automata (NFA), Moore Machine and Mealy Machine.

What are Finite State Machines?

A FSM can be described using a 5-tuple (∑, S, s0, 𝛿, f), where:

∑ is the non-empty set of input alphabet/symbols
S is the non-empty set of states
s0 is the starting state
𝛿 is the transition function: 𝛿 : S × ∑ -> S (This is a bit different in a NFA, we’ll come back to this in a future post)
F is the set of final/accepting states

A Deterministic Finite Automata (DFA), as the name implies, is deterministic with regards to how the states transition. Every state will have one transition for each input symbol.

Transition diagram of an automata that accepts binary strings divisible by 3 — Figure 3 : Transition Diagram for DFA that accepts binary strings that are divisible by 3 [Image Source]

The above image depicts the deterministic nature of DFA. Each state has one transition for each input alphabet (in this case {0, 1}). In the next section, let’s learn how to implement this in code.

CODING TIME: Let’s make a DFA with Python OOP

Before I get started, there will be a link to the GitHub Repo if want to take a look at the entire source code.

First, we’ll make a class called DFA with a constructor containing some function calls. The functions that we call will help us in populating the DFA’s attributes (tuple).

The helper functions are listed below:

The following functions show how the machine will parse input, change states and determine whether to ACCEPT or REJECT the input string:

The run_machine(in_string) method will parse each input symbol of the input string (in_string) and run the state transition if it exists (using the run_state_transition(input_symbol)). After each transition, it’ll check if the new state is REJECT (if it exists). If all of the input string is parsed, it will check if the current state is in the ACCEPT states. If it is, the machine will return True on the input string, else it will return False.

Finally, we have our main function that will add some user friendliness to our entire code. Let’s implement a DFA that recognizes binary strings that are divisible by 3 as shown in Figure 3.

Creating the DFA

$ py DFA.py
Deterministic Finite State Machine.
Enter list of states separated by spaces: q0 q1 q2
STATES : ['q0', 'q1', 'q2']
Enter input alphabet separated by spaces: 0 1
ALPHABET : ['0', '1']
Enter transitions for state q0. If required, use 'REJECT'.
CURRENT STATE : q0      INPUT ALPHABET : 0      NEXT STATE : q0
CURRENT STATE : q0      INPUT ALPHABET : 1      NEXT STATE : q1
Enter transitions for state q1. If required, use 'REJECT'.
CURRENT STATE : q1      INPUT ALPHABET : 0      NEXT STATE : q2
CURRENT STATE : q1      INPUT ALPHABET : 1      NEXT STATE : q0
Enter transitions for state q2. If required, use 'REJECT'.
CURRENT STATE : q2      INPUT ALPHABET : 0      NEXT STATE : q1
CURRENT STATE : q2      INPUT ALPHABET : 1      NEXT STATE : q2

TRANSITION FUNCTION Q X SIGMA -> Q
CURRENT STATE   INPUT ALPHABET  NEXT STATE
q0              0               q0
q0              1               q1
q1              0               q2
q1              1               q0
q2              0               q1
q2              1               q2
Enter the START_STATE: q0
Enter the ACCEPT_STATES: q0

Test String ‘0’ [0]

Enter Choice:
1. Replace DFSM
2. Run DFSM on input string
Enter choice : 2
Enter the input string : 0
CURRENT STATE : q0      INPUT SYMBOL : 0         NEXT STATE : q0
ACCEPTED

Test String ‘110’ [6]

Enter Choice:
1. Replace DFSM
2. Run DFSM on input string
Enter choice : 2
Enter the input string : 110
CURRENT STATE : q0      INPUT SYMBOL : 1         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 1         NEXT STATE : q0
CURRENT STATE : q0      INPUT SYMBOL : 0         NEXT STATE : q0
ACCEPTED

Test String ‘10100’ [20]

Enter Choice:
1. Replace DFSM
2. Run DFSM on input string
Enter choice : 2
Enter the input string : 10100
CURRENT STATE : q0      INPUT SYMBOL : 1         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 0         NEXT STATE : q2
CURRENT STATE : q2      INPUT SYMBOL : 1         NEXT STATE : q2
CURRENT STATE : q2      INPUT SYMBOL : 0         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 0         NEXT STATE : q2
REJECTED

Test String ‘100001111’ [271]

Enter Choice:
1. Replace DFSM
2. Run DFSM on input string
Enter choice : 2
Enter the input string : 100001111
CURRENT STATE : q0      INPUT SYMBOL : 1         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 0         NEXT STATE : q2
CURRENT STATE : q2      INPUT SYMBOL : 0         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 0         NEXT STATE : q2
CURRENT STATE : q2      INPUT SYMBOL : 0         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 1         NEXT STATE : q0
CURRENT STATE : q0      INPUT SYMBOL : 1         NEXT STATE : q1
CURRENT STATE : q1      INPUT SYMBOL : 1         NEXT STATE : q0
CURRENT STATE : q0      INPUT SYMBOL : 1         NEXT STATE : q1
REJECTED

0 and 6 are both accepted by the DFA, and 20 and 271 are both rejected by the DFA. The code implementation works!

This concludes the first entry to Automata Theory in Python. We’re not yet done yet with finite state machines, and we’ll go in-depth about Chomsky’s Hierarchy of Languages and Recognized Grammars and their relation to Automata.

GitHub Repo: https://github.com/VijayaGB98/automata-theory-py/tree/master/finite-state-machine/deterministic-finite-automata

References:

Please feel to comment with feedback. I’ll be back soon with another entry.

Update 1: Additional reference added