# 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:

**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

**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:**

## Leave a Reply

You must be logged in to post a comment.