Construction of Finite Automata in Python

In this tutorial, we will learn the basic concepts of finite automata and its applications. We will try to execute it in python programming. We will discuss this topic step by step and solve all the queries related to this.

What are Finite Automata?

Finite Automata is the abstract computational device having a finite amount of memory. It consists of the following parts-

  • A non-empty finite set of states
  • A set of input alphabets
  • State transition function
  • Initial state
  • The final state

Firstly, we have to know some basic definitions related to this topic:

  • Input Alphabet: A set of the basic symbol
  • String: A sequence of symbol over the input alphabet
  • Language: A set of string over some input alphabet

Finite automata can be divided into two parts –

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

The difference between DFA and NFA is that NFA accepts the empty string whereas DFA does not accept empty string. Therefore, all DFA are NFA but all NFA are not DFA.

Automata Programming in Python

The steps required to perform automata programming are :

  • Firstly, determine the total numbers of states and inputs
  • Secondly, transitions for each state
  • Thirdly, set the final state

For instance, let’s do an example:

L={W| W starts with 1 and ends with 0}

Total number of states=4 {q0,q1,q2,q3}

inputs= 0 and 1

Code: Construct finite automata in Python

#import the requirements from the library automata 
from automata.fa.dfa import DFA

#the transition function
dfa=DFA(
    states= {'q0', 'q1', 'q2', 'q3'},
    input_symbols={'0','1'},
    transitions={
        'q0':{'0':'q3','1':'q1'},
        'q1':{'0':'q2','1':'q1'},
        'q2':{'0':'q2','1':'q1'},
        'q3':{'0':'q3','1':'q3'}
    },
    initial_state='q0',
    final_states={'q2'}
)

INPUT:

if(dfa.accepts_input('10000')):
    print("Accepted")
else:
    print("Rejected")

OUTPUT:

Accepted

INPUT:

if(dfa.accepts_input('10001')):
    print("Accepted")
else:
    print("Rejected")

OUTPUT:

Rejected

Explanation:

Firstly, we have initialized that q0 is the initial state. We only accept the string which starts with 1. So, if it starts with zero,  it will not be considered. Therefore, it directs to state q3. After the state q3, if it is getting 0 or 1 whatever, it will not be considered. When q0 gets 1, it goes to state q1.

Therefore q1 gets 1, it will return to q1. If q1 gets 0, it will go to q2 and makes this state final.

After that, q2 gets 0, it will remain the same i.e. come back to q2. If it gets 1, it moves to q1 and so on.

In conclusion, we have understood the concept of finite automata and implemented through Python programming.

You can check our AdaBoost Algorithm for Machine Learning in Python.

Leave a Reply

Your email address will not be published. Required fields are marked *