A program in Python to demonstrate Finite Automata

Hello Everyone! In this tutorial, we will see how can we make a program in Python to work as finite automata. Here a quick review of Finite Automata(FA).

 

Finite Automata

A Finite Automata is a simple machine that recognizes patterns in the input string. If the input string contains the pattern defined by FA it accepts the string otherwise rejects it.
It is of 2 types:

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

The basic difference between DFA & NFA is that:

• For a particular input string, a machine can go to only 1 state in DFA but a machine can go to multiple states in NFA.
• Null transitions are allowed in NFA but not in DFA.

Finite Automata Program in Python

• Regular expression of FA: 101⁺

Accepted Inputs: 101, 1011, 10111, 10111
Rejected Inputs: 100, 010, 000

CODE

def FA(s):
#if the length is less than 3 then it can't be accepted, Therefore end the process.
    if len(s)<3:
        return "Rejected"
#first three characters are fixed. Therefore checking them using index
    if s[0]=='1':
        if s[1]=='0':
            if s[2]=='1':
                # After index 2 only "1" can appear. Therefore break the process if any other character is detected
                for i in range(3,len(s)):
                    if s[i]!='1':
                        return "Refected"
                return "Accepted"
            return "Rejected"
        return "Rejected"
    return "Rejected"

inputs=['1','10101','101','10111','01010',""]
for i in inputs:
    print(FA(i))
    

OUTPUT

Rejected
Refected
Accepted
Accepted
Rejected
Rejected

---

• Regular expression of FA: (a+b)*bba

Accepted Inputs: bba, ababbba, abba
Rejected Inputs: abb, baba,bbb

CODE

def FA(s):
    size=0
#scan complete string and make sure that it contains only 'a' & 'b'
    for i in s:
        if i=='a' or i=='b':
            size+=1
        else:
            return "Rejected"
#After checking that it contains only 'a' & 'b'
#check it's length it should be 3 atleast
    if size>=3:
#check the last 3 elements
        if s[size-3]=='b':
            if s[size-2]=='b':    
                if s[size-1]=='a':
                    return "Accepted"
                return "Rejected"
            return "Rejected"
        return "Rejected"
    return "Rejected"

inputs=['bba', 'ababbba', 'abba','abb', 'baba','bbb','']
for i in inputs:
    print(FA(i))
    

OUTPUT

Accepted
Accepted
Accepted
Rejected
Rejected
Rejected
Rejected

 

HOPE YOU LIKED THIS TUTORIAL!

Also read:

Regular expression in python

re.sub() in Python