SHARE
TWEET

Untitled

a guest Oct 17th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {
  2.  "cells": [
  3.   {
  4.    "cell_type": "code",
  5.    "execution_count": 19,
  6.    "metadata": {},
  7.    "outputs": [],
  8.    "source": [
  9.     "class DFA:\n",
  10.     "    current_state = None;\n",
  11.     "    def __init__(self, states, alphabet, transition_function, start_state, accept_states):\n",
  12.     "        '''\n",
  13.     "        Initialization of the configuration of DFA, which includes states, alphabet, transitions\n",
  14.     "        (as a hashmap), start states, current state and accept state. This is kept as a \"database\"\n",
  15.     "        to solve the overall computation of the DFA. \n",
  16.     "        '''\n",
  17.     "        self.states = states\n",
  18.     "        self.alphabet = alphabet\n",
  19.     "        self.transition_function = transition_function\n",
  20.     "        self.start_state = start_state\n",
  21.     "        self.accept_states = accept_states\n",
  22.     "        self.current_state = start_state\n",
  23.     "        self.state = True\n",
  24.     "        self.inp_res = []\n",
  25.     "        return\n",
  26.     "    \n",
  27.     "    def parse_input(self, input_str):\n",
  28.     "        '''\n",
  29.     "        This function converts the input to a valid input array with three items per array index. \n",
  30.     "        I.e. if you input '101101', it converts this to ['101', '101']. This list is stored in\n",
  31.     "        __init__ as self.inp_res.\n",
  32.     "        '''\n",
  33.     "        l = len(input_str) - 1\n",
  34.     "        index_s = 0\n",
  35.     "        index_e = 3\n",
  36.     "        while index_e <= l:\n",
  37.     "            self.inp_res.append(input_str[index_s:index_e])\n",
  38.     "            index_s += 3\n",
  39.     "            index_e += 3\n",
  40.     "        if index_e >= l:\n",
  41.     "            self.inp_res.append(input_str[index_s:])\n",
  42.     "        return self.input_traverse(self.inp_res)\n",
  43.     "    \n",
  44.     "    def transition(self, input_value):\n",
  45.     "        '''\n",
  46.     "        This function allows us to transition between the various states in our dfa to deduce \n",
  47.     "        acceptance or rejection. \n",
  48.     "        '''\n",
  49.     "        if input_value in dfa[self.current_state]:\n",
  50.     "            current = dfa[self.current_state][input_value]\n",
  51.     "            self.current_state = current\n",
  52.     "        else:\n",
  53.     "            self.state = False\n",
  54.     "        return\n",
  55.     "    \n",
  56.     "    def is_accept_state(self):\n",
  57.     "        '''\n",
  58.     "        Function checks whether a state is an accept state or reject state. This can be incorporated\n",
  59.     "        in other functions of the code, but I wished to keep it clean and break it down\n",
  60.     "        as much as possible. \n",
  61.     "        '''\n",
  62.     "        return self.current_state in accept_states if self.state == True else False;\n",
  63.     "    \n",
  64.     "    def go_initial(self):\n",
  65.     "        '''\n",
  66.     "        This function is the initialization of the start state and used in the input traversal function\n",
  67.     "        below.\n",
  68.     "        '''\n",
  69.     "        self.current_state = self.start_state;\n",
  70.     "        return\n",
  71.     "    \n",
  72.     "    def input_traverse(self, input_list):\n",
  73.     "        '''\n",
  74.     "        This function traverses the input list curated in the parse_input function to further transition \n",
  75.     "        if the input is in our alphabet, and last, check if the input is the last one and accepted. \n",
  76.     "        '''\n",
  77.     "        self.go_initial()\n",
  78.     "        for inp in input_list:\n",
  79.     "            if inp not in self.alphabet:\n",
  80.     "                return (\"Input not recognized\")\n",
  81.     "            self.transition(inp)\n",
  82.     "            continue\n",
  83.     "        return self.is_accept_state()\n",
  84.     "    pass\n",
  85.     "\n"
  86.    ]
  87.   },
  88.   {
  89.    "cell_type": "code",
  90.    "execution_count": 20,
  91.    "metadata": {},
  92.    "outputs": [],
  93.    "source": [
  94.     "###\n",
  95.     "### CONFIGURATION\n",
  96.     "###\n",
  97.     "\n",
  98.     "states = {0, 1};\n",
  99.     "alphabet = {'000', '101', '011', '110', '111', '010', '100', '001'};\n",
  100.     "dfa = {\n",
  101.     "    0: {'000': 0, '101': 0, '011': 0, '110': 1},\n",
  102.     "   1: {'111': 1, '010': 1, '100': 1, '001': 0}\n",
  103.     "}\n",
  104.     "start_state = 0;\n",
  105.     "accept_states = {0};\n"
  106.    ]
  107.   },
  108.   {
  109.    "cell_type": "code",
  110.    "execution_count": 21,
  111.    "metadata": {},
  112.    "outputs": [
  113.     {
  114.      "name": "stdout",
  115.      "output_type": "stream",
  116.      "text": [
  117.       "True\n",
  118.       "Input not recognized\n",
  119.       "False\n",
  120.       "Input not recognized\n",
  121.       "Input not recognized\n",
  122.       "False\n",
  123.       "True\n"
  124.      ]
  125.     }
  126.    ],
  127.    "source": [
  128.     "###\n",
  129.     "### TESTCASES\n",
  130.     "###\n",
  131.     "\n",
  132.     "# Testcase 1\n",
  133.     "dfa_config_1 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  134.     "inp_arr_1 = '110100001'\n",
  135.     "print (dfa_config_1.parse_input(inp_arr_1));\n",
  136.     "\n",
  137.     "\n",
  138.     "# Testcase 2\n",
  139.     "dfa_config_2 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  140.     "inp_arr_2 = 'abba'\n",
  141.     "print (dfa_config_2.parse_input(inp_arr_2));\n",
  142.     "\n",
  143.     "# Testcase 3\n",
  144.     "dfa_config_3 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  145.     "inp_arr_3 = '011110'\n",
  146.     "print (dfa_config_3.parse_input(inp_arr_3));\n",
  147.     "\n",
  148.     "# Testcase 4\n",
  149.     "dfa_config_4 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  150.     "inp_arr_4 = '01'\n",
  151.     "print (dfa_config_4.parse_input(inp_arr_4));\n",
  152.     "\n",
  153.     "# Testcase 5\n",
  154.     "dfa_config_5 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  155.     "inp_arr_5 = '@@@'\n",
  156.     "print (dfa_config_5.parse_input(inp_arr_5));\n",
  157.     "\n",
  158.     "# Testcase 6\n",
  159.     "dfa_config_6 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  160.     "inp_arr_6 = '110'\n",
  161.     "print (dfa_config_6.parse_input(inp_arr_6));\n",
  162.     "\n",
  163.     "# Testcase 7\n",
  164.     "dfa_config_7 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
  165.     "inp_arr_7 = '000'\n",
  166.     "print (dfa_config_7.parse_input(inp_arr_7));\n"
  167.    ]
  168.   },
  169.   {
  170.    "cell_type": "code",
  171.    "execution_count": null,
  172.    "metadata": {},
  173.    "outputs": [],
  174.    "source": []
  175.   }
  176.  ],
  177.  "metadata": {
  178.   "kernelspec": {
  179.    "display_name": "Python 3",
  180.    "language": "python",
  181.    "name": "python3"
  182.   },
  183.   "language_info": {
  184.    "codemirror_mode": {
  185.     "name": "ipython",
  186.     "version": 3
  187.    },
  188.    "file_extension": ".py",
  189.    "mimetype": "text/x-python",
  190.    "name": "python",
  191.    "nbconvert_exporter": "python",
  192.    "pygments_lexer": "ipython3",
  193.    "version": "3.7.1"
  194.   }
  195.  },
  196.  "nbformat": 4,
  197.  "nbformat_minor": 2
  198. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top