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).
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:
- Deterministic Finite Automata(DFA)
- 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
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=='1': if s=='0': if s=='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))
Rejected Refected Accepted Accepted Rejected Rejected
- Regular expression of FA: (a+b)*bba
Accepted Inputs: bba, ababbba, abba
Rejected Inputs: abb, baba,bbb
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))
Accepted Accepted Accepted Rejected Rejected Rejected Rejected
HOPE YOU LIKED THIS TUTORIAL!