{
 "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
}