{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DFA:\n",
    "    current_state = None;\n",
    "    def __init__(self, states, alphabet, transition_function, start_state, accept_states):\n",
    "        '''\n",
    "        Initialization of the configuration of DFA, which includes states, alphabet, transitions\n",
    "        (as a hashmap), start states, current state and accept state. This is kept as a \"database\"\n",
    "        to solve the overall computation of the DFA. \n",
    "        '''\n",
    "        self.states = states\n",
    "        self.alphabet = alphabet\n",
    "        self.transition_function = transition_function\n",
    "        self.start_state = start_state\n",
    "        self.accept_states = accept_states\n",
    "        self.current_state = start_state\n",
    "        self.state = True\n",
    "        self.inp_res = []\n",
    "        return\n",
    "    \n",
    "    def parse_input(self, input_str):\n",
    "        '''\n",
    "        This function converts the input to a valid input array with three items per array index. \n",
    "        I.e. if you input '101101', it converts this to ['101', '101']. This list is stored in\n",
    "        __init__ as self.inp_res.\n",
    "        '''\n",
    "        l = len(input_str) - 1\n",
    "        index_s = 0\n",
    "        index_e = 3\n",
    "        while index_e <= l:\n",
    "            self.inp_res.append(input_str[index_s:index_e])\n",
    "            index_s += 3\n",
    "            index_e += 3\n",
    "        if index_e >= l:\n",
    "            self.inp_res.append(input_str[index_s:])\n",
    "        return self.input_traverse(self.inp_res)\n",
    "    \n",
    "    def transition(self, input_value):\n",
    "        '''\n",
    "        This function allows us to transition between the various states in our dfa to deduce \n",
    "        acceptance or rejection. \n",
    "        '''\n",
    "        if input_value in dfa[self.current_state]:\n",
    "            current = dfa[self.current_state][input_value]\n",
    "            self.current_state = current\n",
    "        else:\n",
    "            self.state = False\n",
    "        return\n",
    "    \n",
    "    def is_accept_state(self):\n",
    "        '''\n",
    "        Function checks whether a state is an accept state or reject state. This can be incorporated\n",
    "        in other functions of the code, but I wished to keep it clean and break it down\n",
    "        as much as possible. \n",
    "        '''\n",
    "        return self.current_state in accept_states if self.state == True else False;\n",
    "    \n",
    "    def go_initial(self):\n",
    "        '''\n",
    "        This function is the initialization of the start state and used in the input traversal function\n",
    "        below.\n",
    "        '''\n",
    "        self.current_state = self.start_state;\n",
    "        return\n",
    "    \n",
    "    def input_traverse(self, input_list):\n",
    "        '''\n",
    "        This function traverses the input list curated in the parse_input function to further transition \n",
    "        if the input is in our alphabet, and last, check if the input is the last one and accepted. \n",
    "        '''\n",
    "        self.go_initial()\n",
    "        for inp in input_list:\n",
    "            if inp not in self.alphabet:\n",
    "                return (\"Input not recognized\")\n",
    "            self.transition(inp)\n",
    "            continue\n",
    "        return self.is_accept_state()\n",
    "    pass\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "###\n",
    "### CONFIGURATION\n",
    "###\n",
    "\n",
    "states = {0, 1};\n",
    "alphabet = {'000', '101', '011', '110', '111', '010', '100', '001'};\n",
    "dfa = {\n",
    "    0: {'000': 0, '101': 0, '011': 0, '110': 1},\n",
    "   1: {'111': 1, '010': 1, '100': 1, '001': 0}\n",
    "}\n",
    "start_state = 0;\n",
    "accept_states = {0};\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "Input not recognized\n",
      "False\n",
      "Input not recognized\n",
      "Input not recognized\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "###\n",
    "### TESTCASES\n",
    "###\n",
    "\n",
    "# Testcase 1\n",
    "dfa_config_1 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_1 = '110100001'\n",
    "print (dfa_config_1.parse_input(inp_arr_1));\n",
    "\n",
    "\n",
    "# Testcase 2\n",
    "dfa_config_2 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_2 = 'abba'\n",
    "print (dfa_config_2.parse_input(inp_arr_2));\n",
    "\n",
    "# Testcase 3\n",
    "dfa_config_3 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_3 = '011110'\n",
    "print (dfa_config_3.parse_input(inp_arr_3));\n",
    "\n",
    "# Testcase 4\n",
    "dfa_config_4 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_4 = '01'\n",
    "print (dfa_config_4.parse_input(inp_arr_4));\n",
    "\n",
    "# Testcase 5\n",
    "dfa_config_5 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_5 = '@@@'\n",
    "print (dfa_config_5.parse_input(inp_arr_5));\n",
    "\n",
    "# Testcase 6\n",
    "dfa_config_6 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_6 = '110'\n",
    "print (dfa_config_6.parse_input(inp_arr_6));\n",
    "\n",
    "# Testcase 7\n",
    "dfa_config_7 = DFA(states, alphabet, dfa, start_state, accept_states);\n",
    "inp_arr_7 = '000'\n",
    "print (dfa_config_7.parse_input(inp_arr_7));\n"
   ]
  },
  {
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}