cfg-to-npda.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Context-Free Grammar to Non-deterministic push-down automata Convertor: "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "3f0dcada6caaa18b"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "def cfg_to_npda(cfg):\n",
    "    # Extract productions and start symbol from the given CFG\n",
    "    productions = cfg['productions']\n",
    "    start_symbol = cfg['start_symbol']\n",
    "    \n",
    "    # Initialize transitions list with the starting transition to push the start symbol\n",
    "    transitions = [(0, 'ε', 'ε', 1, start_symbol, 'PUSH')]\n",
    "    alphabet = set()  # Initialize an empty set to track the alphabet\n",
    "    \n",
    "    # Iterate over each variable and its corresponding production list in the CFG\n",
    "    for variable, production_list in productions.items():\n",
    "        for rhs in production_list:\n",
    "            # Iterate over each character in the production's right-hand side\n",
    "            for char in rhs:\n",
    "                # If the character is not in the alphabet and not a variable, add it to the alphabet\n",
    "                if char not in alphabet and char not in productions.keys():\n",
    "                    alphabet.add(char)\n",
    "                    # Add a transition to consume the terminal character\n",
    "                    transitions.append((1,  char, char, 1, 'ε', 'POP'))\n",
    "            # Handle epsilon (ε) productions\n",
    "            if rhs == 'ε':\n",
    "                # Add a transition to pop the variable when ε is encountered\n",
    "                transitions.append((1, 'ε', variable, 1, 'ε', 'POP'))\n",
    "            else:\n",
    "                # For non-epsilon productions, reverse the RHS and push it onto the stack\n",
    "                new_stack_symbols = ''.join(reversed(rhs))\n",
    "                transitions.append((1, 'ε', variable, 1, new_stack_symbols, 'PUSH'))\n",
    "                \n",
    "    # Add a transition to the accepting state (state 2) when the stack's bottom symbol is encountered\n",
    "    transitions.append((1, 'ε', '$', 2, 'ε', 'NONE'))\n",
    "    \n",
    "    # Return the list of transitions for the NPDA\n",
    "    return transitions"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-07-01T22:29:02.802712Z",
     "start_time": "2024-07-01T22:29:02.799975Z"
    }
   },
   "id": "d33ec0f75e12b911",
   "execution_count": 36
  },
  {
   "cell_type": "markdown",
   "source": [
    "Input Section:"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "41c06cbf562238c6"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NPDA Transitions:\n",
      "(0, 'ε', 'ε', 1, 'S', 'PUSH')\n",
      "(1, 'a', 'a', 1, 'ε', 'POP')\n",
      "(1, 'b', 'b', 1, 'ε', 'POP')\n",
      "(1, 'ε', 'S', 1, 'bAa', 'PUSH')\n",
      "(1, 'ε', 'A', 1, 'bSa', 'PUSH')\n",
      "(1, 'ε', 'ε', 1, 'ε', 'POP')\n",
      "(1, 'ε', 'A', 1, 'ε', 'POP')\n",
      "(1, 'ε', '$', 2, 'ε', 'NONE')\n",
      "Final state: 2\n"
     ]
    }
   ],
   "source": [
    "# Example CFG defined as a dictionary\n",
    "cfg = {\n",
    "    'start_symbol': 'S',  # The start symbol of the CFG\n",
    "    'productions': {\n",
    "        'S': ['aAb'],  # Productions for the variable S\n",
    "        'A': ['aSb', 'ε']  # Productions for the variable A, including epsilon (ε) production\n",
    "    }\n",
    "}\n",
    "\n",
    "# Convert the CFG to NPDA transitions using the cfg_to_npda function\n",
    "npda_transitions = cfg_to_npda(cfg)\n",
    "\n",
    "# Print the NPDA transitions\n",
    "print(\"NPDA Transitions:\")\n",
    "for transition in npda_transitions:\n",
    "    # Iterate over each transition and print it\n",
    "    print(transition)\n",
    "\n",
    "# Print the final accepting state of the NPDA\n",
    "print(f\"Final state: {2}\")"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-07-01T22:29:03.704867Z",
     "start_time": "2024-07-01T22:29:03.699885Z"
    }
   },
   "id": "96e740d3b8fece40",
   "execution_count": 37
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}