Pushdown Automata Implementation
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A Simple Implementation of Push Down Automaton:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Defining the 6 tuples:\n",
"> * Q-->finite set of sets\n",
"> * Sigma-->finite set of input alphabet\n",
"> * Gamma-->finite set of stack alphabet\n",
"> * Delta-->transition relation\n",
"> * Q0-->start state\n",
"> * Z-->initial stack symbol\n",
"> * F-->set of accepting states\n",
"\n",
"# Defining the states:\n",
"\n",
"* state 0: starting state\n",
"\n",
"* state 1:From state 0 whenever it sees a 1 or 2, it moves to state 1+pushes the element onto the stack\n",
"* state 1:From state 1 whenever it sees a 1 or 2, it remains in state 1+pushes the element onto the stack\n",
"\n",
"* state 2:From state 1 whenever it sees a 0, it moves to state 2+pops from the stack\n",
"* state 2:From state 1 whenever it sees a 0, it remains in state 2+pops from the stack\n",
"\n",
"* state 3:From state 0, if it sees a 0,it moves to state 3,the rejected state\n",
"* state 3:From state 2, if it sees a 1 or 2 , it moves to state 3, the rejected state\n",
"* state 3:If at the end, the stack is not empty, it moves to state 3,the rejected state\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Enter the String:123456\n",
"The String is rejected\n"
]
}
],
"source": [
"#stack functions\n",
"def push(a,list1):\n",
" #pushing to the stack/adding to the top of the stack\n",
" list1.append(a)\n",
" return 1\n",
"\n",
"def pop(list1):\n",
" #for poping from the stack/removing the top element of the stack\n",
" index=len(list1)-1\n",
" if (index>0):\n",
" list1.pop(index)\n",
" return 1\n",
" else:\n",
" return 0\n",
"\n",
"# Q={0,1,2,3}\n",
"# Sigma={0,1,2}\n",
"# Starting state={0}\n",
"# Z=#\n",
"# F={2}\n",
"\n",
"#setting the initial stack symbol\n",
"stack=['#']\n",
"#setting the starting state\n",
"state=0\n",
"\n",
"#taking the input\n",
"input_string=input('Enter the String:')\n",
"\n",
"#performing the operations\n",
"l=len(input_string)\n",
"i=0\n",
"if l%2==0:\n",
" while i<l//2:\n",
" letter=int(input_string[i])\n",
" #print(letter)\n",
" if letter in [1,2]:\n",
" push(letter,stack)\n",
" state=1\n",
" #print(\">state=1\")\n",
" else :\n",
" state=3\n",
" #print(\">1.state=3\")\n",
" break\n",
" i+=1\n",
" \n",
" while i<l:\n",
" letter=int(input_string[i])\n",
" #print(letter)\n",
" if state==3:\n",
" break\n",
" if letter==0:\n",
" state=2\n",
" #print(\">2.state=2\")\n",
" pop(stack)\n",
" else:\n",
" state=3\n",
" #print(\">2.state=3\")\n",
" break\n",
" i+=1\n",
"else:\n",
" state=3\n",
" #print(\"3state=3\")\n",
" \n",
"if state==2 and len(stack)!=1:\n",
" state=3\n",
" \n",
"#print(state)\n",
"#print(len(stack))\n",
"\n",
"#checking the final state and displaying the result\n",
"if(state==2):\n",
" print(\"The String is accepted\")\n",
"else:\n",
" print(\"The String is rejected\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
About this Algorithm
A Simple Implementation of Push Down Automaton:
Defining the 6 tuples:
- Q-->finite set of sets
- Sigma-->finite set of input alphabet
- Gamma-->finite set of stack alphabet
- Delta-->transition relation
- Q0-->start state
- Z-->initial stack symbol
- F-->set of accepting states
Defining the states:
state 0: starting state
state 1:From state 0 whenever it sees a 1 or 2, it moves to state 1+pushes the element onto the stack
state 1:From state 1 whenever it sees a 1 or 2, it remains in state 1+pushes the element onto the stack
state 2:From state 1 whenever it sees a 0, it moves to state 2+pops from the stack
state 2:From state 1 whenever it sees a 0, it remains in state 2+pops from the stack
state 3:From state 0, if it sees a 0,it moves to state 3,the rejected state
state 3:From state 2, if it sees a 1 or 2 , it moves to state 3, the rejected state
state 3:If at the end, the stack is not empty, it moves to state 3,the rejected state
#stack functions
def push(a,list1):
#pushing to the stack/adding to the top of the stack
list1.append(a)
return 1
def pop(list1):
#for poping from the stack/removing the top element of the stack
index=len(list1)-1
if (index>0):
list1.pop(index)
return 1
else:
return 0
# Q={0,1,2,3}
# Sigma={0,1,2}
# Starting state={0}
# Z=#
# F={2}
#setting the initial stack symbol
stack=['#']
#setting the starting state
state=0
#taking the input
input_string=input('Enter the String:')
#performing the operations
l=len(input_string)
i=0
if l%2==0:
while i<l//2:
letter=int(input_string[i])
#print(letter)
if letter in [1,2]:
push(letter,stack)
state=1
#print(">state=1")
else :
state=3
#print(">1.state=3")
break
i+=1
while i<l:
letter=int(input_string[i])
#print(letter)
if state==3:
break
if letter==0:
state=2
#print(">2.state=2")
pop(stack)
else:
state=3
#print(">2.state=3")
break
i+=1
else:
state=3
#print("3state=3")
if state==2 and len(stack)!=1:
state=3
#print(state)
#print(len(stack))
#checking the final state and displaying the result
if(state==2):
print("The String is accepted")
else:
print("The String is rejected")Enter the String:123456
The String is rejected
