The Algorithms logo
The Algorithms
AboutDonate

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&gt;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&lt;l//2:
        letter=int(input_string[i])
        #print(letter)
        if letter in [1,2]:
            push(letter,stack)
            state=1
            #print("&gt;state=1")
        else :
            state=3
            #print("&gt;1.state=3")
            break
        i+=1
    
    while i&lt;l:
        letter=int(input_string[i])
        #print(letter)
        if state==3:
            break
        if letter==0:
            state=2
            #print("&gt;2.state=2")
            pop(stack)
        else:
            state=3
            #print("&gt;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