README.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "affiliated-islam",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Visual Automata\n",
    "\n",
    "[![Latest Version](https://img.shields.io/pypi/v/visual-automata.svg)](https://pypi.python.org/pypi/visual-automata/)\n",
    "[![Supported Python versions](https://img.shields.io/pypi/pyversions/visual-automata.svg)](https://pypi.python.org/pypi/visual-automata/)\n",
    "[![Downloads](https://pepy.tech/badge/visual-automata)](https://pepy.tech/project/visual-automata)\n",
    "[![Coverage](https://img.shields.io/codecov/c/github/lewiuberg/visual-automata?color=blue)](https://app.codecov.io/gh/lewiuberg/visual-automata)\n",
    "\n",
    "Copyright 2021 [Lewi Lie Uberg](https://uberg.me/)\\\n",
    "_Released under the MIT license_\n",
    "\n",
    "Visual Automata is a Python 3 library built as a wrapper for the [Automata](https://github.com/caleb531/automata) library to add more visualization features.\n",
    "\n",
    "## Contents\n",
    "\n",
    "- [Visual Automata](#visual-automata)\n",
    "  - [Contents](#contents)\n",
    "  - [Prerequisites](#prerequisites)\n",
    "  - [Installing](#installing)\n",
    "  - [Finite Automaton](#finite-automaton-fa)\n",
    "    - [VisualDFA](#visualdfa)\n",
    "      - [Importing](#importing)\n",
    "      - [Instantiating DFAs](#instantiating-dfas)\n",
    "      - [Converting](#converting)\n",
    "      - [Transition Table](#transition-table)\n",
    "      - [Minimal-DFA](#minimal-dfa)\n",
    "      - [Check input strings](#check-input-strings)\n",
    "      - [Show Diagram](#show-diagram)\n",
    "    - [VisualNFA](#visualnfa)\n",
    "      - [Importing](#importing-1)\n",
    "      - [Instantiating NFAs](#instantiating-nfas)\n",
    "      - [Converting](#converting-1)\n",
    "      - [Transition Table](#transition-table-1)\n",
    "      - [Eliminate lambda/epsilon](#eliminate-lambdaepsilon)\n",
    "      - [Check input strings](#check-input-strings-1)\n",
    "      - [Show Diagram](#show-diagram-1)\n",
    "  - [Authors](#authors)\n",
    "  - [License](#license)\n",
    "  - [Acknowledgments](#acknowledgments)\n",
    "\n",
    "## Citation\n",
    "\n",
    "### APA\n",
    "\n",
    "```apa\n",
    "Lie Uberg, L. (2021). Visual Automata (Version 1.1.1) [Computer software]. https://github.com/lewiuberg/visual-automata\n",
    "```\n",
    "\n",
    "### BibTex\n",
    "\n",
    "```BibTex\n",
    "@misc{Lie_Uberg_Visual_Automata_2021,\n",
    "author = {Lie Uberg, Lewi},\n",
    "month = {4},\n",
    "title = {{Visual Automata}},\n",
    "url = {https://github.com/lewiuberg/visual-automata},\n",
    "year = {2021}\n",
    "}\n",
    "```\n",
    "\n",
    "hub.com/pandas-dev/pandas)\\\n",
    "[`pip install graphviz`](https://github.com/xflr6/graphviz)\\\n",
    "[`pip install colormath`](https://github.com/gtaylor/python-colormath)\\\n",
    "[`pip install jupyterlab`](https://github.com/jupyterlab/jupyterlab)\n",
    "\n",
    "## Installing\n",
    "\n",
    "[`pip install visual-automata`](https://pypi.org/project/visual-automata/)\n",
    "\n",
    "## Finite Automaton (FA)\n",
    "\n",
    "### VisualDFA\n",
    "\n",
    "#### Importing\n",
    "\n",
    "Import needed classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "iraqi-selling",
   "metadata": {},
   "outputs": [],
   "source": [
    "from automata.fa.dfa import DFA\n",
    "\n",
    "from visual_automata.fa.dfa import VisualDFA"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "stone-agriculture",
   "metadata": {},
   "source": [
    "#### Instantiating DFAs\n",
    "\n",
    "Define an visual_automata DFA that can accept any string ending with 00 or 11."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "hundred-childhood",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa = VisualDFA(\n",
    "    states={\"q0\", \"q1\", \"q2\", \"q3\", \"q4\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\"0\": \"q3\", \"1\": \"q1\"},\n",
    "        \"q1\": {\"0\": \"q3\", \"1\": \"q2\"},\n",
    "        \"q2\": {\"0\": \"q3\", \"1\": \"q2\"},\n",
    "        \"q3\": {\"0\": \"q4\", \"1\": \"q1\"},\n",
    "        \"q4\": {\"0\": \"q4\", \"1\": \"q1\"},\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"q2\", \"q4\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "through-dayton",
   "metadata": {},
   "source": [
    "#### Converting\n",
    "\n",
    "An automata-lib DFA can be converted to a VisualDFA.\n",
    "\n",
    "Define an automata-lib DFA that can accept any string ending with 00 or 11."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "artificial-collective",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa = DFA(\n",
    "    states={\"q0\", \"q1\", \"q2\", \"q3\", \"q4\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\"0\": \"q3\", \"1\": \"q1\"},\n",
    "        \"q1\": {\"0\": \"q3\", \"1\": \"q2\"},\n",
    "        \"q2\": {\"0\": \"q3\", \"1\": \"q2\"},\n",
    "        \"q3\": {\"0\": \"q4\", \"1\": \"q1\"},\n",
    "        \"q4\": {\"0\": \"q4\", \"1\": \"q1\"},\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"q2\", \"q4\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "engaged-samba",
   "metadata": {},
   "source": [
    "Convert automata-lib DFA to VisualDFA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "rental-vector",
   "metadata": {},
   "outputs": [],
   "source": [
    "dfa = VisualDFA(dfa)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "satisfied-virus",
   "metadata": {},
   "source": [
    "#### Transition Table\n",
    "\n",
    "Outputs the transition table for the given DFA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ethical-batch",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→q0</th>\n",
       "      <td>q3</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q1</th>\n",
       "      <td>q3</td>\n",
       "      <td>*q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>*q2</th>\n",
       "      <td>q3</td>\n",
       "      <td>*q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q3</th>\n",
       "      <td>*q4</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>*q4</th>\n",
       "      <td>*q4</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       0    1\n",
       "→q0   q3   q1\n",
       "q1    q3  *q2\n",
       "*q2   q3  *q2\n",
       "q3   *q4   q1\n",
       "*q4  *q4   q1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "intended-plaintiff",
   "metadata": {},
   "source": [
    "```text\n",
    "       0    1\n",
    "→q0   q3   q1\n",
    "q1    q3  *q2\n",
    "*q2   q3  *q2\n",
    "q3   *q4   q1\n",
    "*q4  *q4   q1\n",
    "```\n",
    "\n",
    "#### Minimal-DFA\n",
    "\n",
    "Creates a minimal DFA which accepts the same inputs as the old one. Unreachable states are removed and equivalent states are merged. States are renamed by default."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "central-street",
   "metadata": {},
   "outputs": [],
   "source": [
    "new_dfa = VisualDFA(\n",
    "    states={'q0', 'q1', 'q2'},\n",
    "    input_symbols={'0', '1'},\n",
    "    transitions={\n",
    "        'q0': {'0': 'q0', '1': 'q1'},\n",
    "        'q1': {'0': 'q0', '1': 'q2'},\n",
    "        'q2': {'0': 'q2', '1': 'q1'}\n",
    "    },\n",
    "    initial_state='q0',\n",
    "    final_states={'q1'}\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "atomic-hands",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→q0</th>\n",
       "      <td>q0</td>\n",
       "      <td>*q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>*q1</th>\n",
       "      <td>q0</td>\n",
       "      <td>q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q2</th>\n",
       "      <td>q2</td>\n",
       "      <td>*q1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      0    1\n",
       "→q0  q0  *q1\n",
       "*q1  q0   q2\n",
       "q2   q2  *q1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_dfa.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "right-success",
   "metadata": {},
   "source": [
    "```text\n",
    "      0    1\n",
    "→q0  q0  *q1\n",
    "*q1  q0   q2\n",
    "q2   q2  *q1\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "universal-framework",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"276pt\" height=\"84pt\"\n",
       " viewBox=\"0.00 0.00 275.59 84.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 80)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-80 271.59,-80 271.59,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-23.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60.1\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.78,-23.5C7.28,-23.5 19.64,-23.5 31.78,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.96,-26.47 40.46,-23.5 31.96,-20.52 31.96,-26.47\"/>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.63,-42.02C52.53,-51.95 54.68,-61 60.1,-61 63.82,-61 66,-56.72 66.65,-50.82\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"69.62,-50.49 66.57,-42.02 63.67,-50.55 69.62,-50.49\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-64.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"154.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"154.09\" cy=\"-23.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"154.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.72,-23.5C91.69,-23.5 107.55,-23.5 121.47,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"121.77,-26.47 130.27,-23.5 121.77,-20.52 121.77,-26.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.1\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M133.83,-11.16C123.27,-5.86 109.86,-1.5 97.6,-4.5 93.2,-5.57 88.74,-7.28 84.52,-9.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"82.98,-6.69 76.79,-13.23 85.71,-11.98 82.98,-6.69\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.1\" y=\"-8.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"248.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"248.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M177.84,-23.5C190.46,-23.5 206.25,-23.5 219.57,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.83,-26.47 228.33,-23.5 219.83,-20.52 219.83,-26.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q1 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M231.4,-13.23C225.19,-9.73 217.81,-6.26 210.59,-4.5 201.2,-2.2 191.14,-4.22 182.2,-7.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"180.92,-4.99 174.36,-11.16 183.34,-10.42 180.92,-4.99\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-8.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M240.24,-41.63C238.77,-51.71 241.39,-61 248.09,-61 252.8,-61 255.5,-56.41 256.17,-50.18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"259.15,-50.05 255.95,-41.63 253.2,-50.21 259.15,-50.05\"/>\n",
       "<text text-anchor=\"middle\" x=\"248.09\" y=\"-64.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x11b4cef98>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_dfa.show_diagram()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fluid-operator",
   "metadata": {},
   "source": [
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/new_dfa.png?raw=true \"new_dfa\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "israeli-territory",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"226pt\" height=\"120pt\"\n",
       " viewBox=\"0.00 0.00 225.89 120.29\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 116.29)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-116.29 221.89,-116.29 221.89,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-39.65\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- {q0,q2} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>{q0,q2}</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"80.25\" cy=\"-39.65\" rx=\"39.79\" ry=\"39.79\"/>\n",
       "<text text-anchor=\"middle\" x=\"80.25\" y=\"-35.95\" font-family=\"Times,serif\" font-size=\"14.00\">{q0,q2}</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;{q0,q2} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;{q0,q2}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.66,-39.65C6.83,-39.65 18.42,-39.65 31.59,-39.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.91,-42.62 40.41,-39.65 31.91,-36.67 31.91,-42.62\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"194.39\" cy=\"-39.65\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"194.39\" cy=\"-39.65\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"194.39\" y=\"-35.95\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;{q0,q2} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q1&#45;&gt;{q0,q2}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M170.57,-39.65C158.58,-39.65 143.41,-39.65 129,-39.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"128.65,-36.67 120.15,-39.65 128.65,-42.62 128.65,-36.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"145.39\" y=\"-43.45\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;{q0,q2} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;{q0,q2}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M173.41,-28.16C167.06,-25.09 159.87,-22.2 152.89,-20.65 143.76,-18.61 134.03,-19.26 124.78,-21.25\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"123.94,-18.39 116.46,-23.4 125.43,-24.15 123.94,-18.39\"/>\n",
       "<text text-anchor=\"middle\" x=\"145.39\" y=\"-24.45\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- {q0,q2}&#45;&gt;q1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>{q0,q2}&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M117.6,-53.63C128.88,-56.39 141.37,-57.84 152.89,-55.65 156.76,-54.91 160.72,-53.81 164.59,-52.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"165.87,-55.23 172.82,-49.5 163.82,-49.65 165.87,-55.23\"/>\n",
       "<text text-anchor=\"middle\" x=\"145.39\" y=\"-60.45\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- {q0,q2}&#45;&gt;{q0,q2} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>{q0,q2}&#45;&gt;{q0,q2}</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.41,-77.9C69.84,-88.85 73.45,-97.29 80.25,-97.29 85.13,-97.29 88.37,-92.93 89.96,-86.41\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"92.93,-86.71 91.08,-77.9 87.03,-85.94 92.93,-86.71\"/>\n",
       "<text text-anchor=\"middle\" x=\"80.25\" y=\"-101.09\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x11b5400f0>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimal_dfa = VisualDFA.minify(new_dfa)\n",
    "minimal_dfa.show_diagram()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alpine-cigarette",
   "metadata": {},
   "source": [
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/minimal_dfa.png?raw=true \"minimal_dfa\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "communist-portland",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→{q0,q2}</th>\n",
       "      <td>{q0,q2}</td>\n",
       "      <td>*q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>*q1</th>\n",
       "      <td>{q0,q2}</td>\n",
       "      <td>{q0,q2}</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                0        1\n",
       "→{q0,q2}  {q0,q2}      *q1\n",
       "*q1       {q0,q2}  {q0,q2}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimal_dfa.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "elder-child",
   "metadata": {},
   "source": [
    "```text\n",
    "                0        1\n",
    "→{q0,q2}  {q0,q2}      *q1\n",
    "*q1       {q0,q2}  {q0,q2}\n",
    "```\n",
    "\n",
    "#### Check input strings\n",
    "\n",
    "`1001` does not end with `00` or `11`, and is therefore `Rejected`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "likely-terminal",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Rejected]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q3</td>\n",
       "      <td>0</td>\n",
       "      <td>*q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>*q4</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Rejected]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1                →q0             1         q1\n",
       "2                 q1             0         q3\n",
       "3                 q3             0        *q4\n",
       "4                *q4             1         q1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.input_check(\"1001\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "trying-expense",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Rejected]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1                →q0             1         q1\n",
    "2                 q1             0         q3\n",
    "3                 q3             0        *q4\n",
    "4                *q4             1         q1\n",
    "```\n",
    "\n",
    "`10011` does end with `11`, and is therefore `Accepted`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "excited-angle",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Accepted]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q3</td>\n",
       "      <td>0</td>\n",
       "      <td>*q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>*q4</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>q1</td>\n",
       "      <td>1</td>\n",
       "      <td>*q2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Accepted]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1                →q0             1         q1\n",
       "2                 q1             0         q3\n",
       "3                 q3             0        *q4\n",
       "4                *q4             1         q1\n",
       "5                 q1             1        *q2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.input_check(\"10011\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "intimate-hayes",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Accepted]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1                →q0             1         q1\n",
    "2                 q1             0         q3\n",
    "3                 q3             0        *q4\n",
    "4                *q4             1         q1\n",
    "5                 q1             1        *q2\n",
    "```\n",
    "\n",
    "#### Show Diagram\n",
    "\n",
    "For IPython `dfa.show_diagram()` may be used.\\\n",
    "For a python script `dfa.show_diagram(view=True)` may be used to automatically view the graph as a PDF file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "adjusted-hungary",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"464pt\" height=\"256pt\"\n",
       " viewBox=\"0.00 0.00 463.58 256.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 252.5)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-252.5 459.58,-252.5 459.58,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-19.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60.1\" cy=\"-19.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-15.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.78,-19.5C7.28,-19.5 19.64,-19.5 31.78,-19.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.96,-22.47 40.46,-19.5 31.96,-16.52 31.96,-22.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"150.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"150.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M75.24,-32.51C89.69,-45.82 112.28,-66.61 128.68,-81.7\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"127.01,-84.22 135.28,-87.78 131.04,-79.84 127.01,-84.22\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.1\" y=\"-68.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"338.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"338.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q3</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.62,-22.57C120.5,-29.7 221.15,-49.2 300.59,-80.5 304.85,-82.18 309.24,-84.25 313.43,-86.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"312.27,-89.18 321.16,-90.63 315.12,-83.95 312.27,-89.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"195.09\" y=\"-52.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"244.09\" cy=\"-156.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"244.09\" cy=\"-156.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"244.09\" y=\"-152.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M167.12,-110.25C180.66,-118.49 200.33,-130.47 216.26,-140.17\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"214.94,-142.84 223.74,-144.72 218.03,-137.76 214.94,-142.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"195.09\" y=\"-133.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.61,-100.5C202.53,-100.5 271.39,-100.5 309.76,-100.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"309.87,-103.47 318.37,-100.5 309.87,-97.52 309.87,-103.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"244.09\" y=\"-104.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M235.27,-178.7C234.31,-189 237.25,-198 244.09,-198 248.9,-198 251.79,-193.55 252.74,-187.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"255.72,-187.26 252.91,-178.7 249.77,-187.14 255.72,-187.26\"/>\n",
       "<text text-anchor=\"middle\" x=\"244.09\" y=\"-201.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M264.6,-144.62C278.88,-135.93 298.34,-124.09 313.49,-114.86\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"315.26,-117.27 320.98,-110.3 312.17,-112.18 315.26,-117.27\"/>\n",
       "<text text-anchor=\"middle\" x=\"293.09\" y=\"-133.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q1 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M319.36,-94.24C305.47,-89.69 285.57,-83.91 267.59,-81.5 246.89,-78.72 241.29,-78.72 220.59,-81.5 205.99,-83.46 190.11,-87.64 177.22,-91.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"176.03,-88.84 168.82,-94.24 177.82,-94.51 176.03,-88.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"244.09\" y=\"-85.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"432.08\" cy=\"-170.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"432.08\" cy=\"-170.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-166.8\" font-family=\"Times,serif\" font-size=\"14.00\">q4</text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M354.28,-112.06C368.3,-122.73 389.39,-138.77 405.93,-151.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"404.13,-153.73 412.7,-156.51 407.74,-148.99 404.13,-153.73\"/>\n",
       "<text text-anchor=\"middle\" x=\"383.09\" y=\"-141.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M412.33,-183.67C373.88,-208.91 284.38,-258.42 220.59,-221.5 186.01,-201.48 167.14,-157.03 158.09,-127.94\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.85,-126.76 155.59,-119.45 155.14,-128.44 160.85,-126.76\"/>\n",
       "<text text-anchor=\"middle\" x=\"293.09\" y=\"-237.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q4 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M423.26,-192.7C422.3,-203 425.24,-212 432.08,-212 436.9,-212 439.78,-207.55 440.73,-201.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"443.71,-201.26 440.91,-192.7 437.76,-201.14 443.71,-201.26\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-215.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x11b540f60>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.show_diagram()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "flexible-knife",
   "metadata": {},
   "source": [
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/dfa.png?raw=true \"dfa\")\n",
    "\n",
    "The `show_diagram` method also accepts input strings, and will return a graph with gradient `red` arrows for `Rejected` results, and gradient `green` arrows for `Accepted` results. It will also display a table with transitions states stepwise. The steps in this table will correspond with the `[number]` over each traversed arrow.\n",
    "\n",
    "Please note that for visual purposes additional arrows are added if a transition is traversed more than once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "iraqi-quarter",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Rejected]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q3</td>\n",
       "      <td>0</td>\n",
       "      <td>*q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>*q4</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Rejected]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1                →q0             1         q1\n",
       "2                 q1             0         q3\n",
       "3                 q3             0        *q4\n",
       "4                *q4             1         q1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"479pt\" height=\"287pt\"\n",
       " viewBox=\"0.00 0.00 478.58 287.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283.5)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283.5 474.58,-283.5 474.58,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-19.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60.1\" cy=\"-19.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-15.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.78,-19.5C7.28,-19.5 19.64,-19.5 31.78,-19.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.96,-22.47 40.46,-19.5 31.96,-16.52 31.96,-22.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"155.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#ffff00\" stroke-width=\"2.5\" d=\"M75.63,-32.15C91.05,-45.59 115.57,-66.94 133.1,-82.21\"/>\n",
       "<polygon fill=\"#ffff00\" stroke=\"#ffff00\" stroke-width=\"2.5\" points=\"131.3,-84.59 139.67,-87.93 135.21,-80.1 131.3,-84.59\"/>\n",
       "<text text-anchor=\"middle\" x=\"107.6\" y=\"-85.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [1]</text>\n",
       "<text text-anchor=\"middle\" x=\"107.6\" y=\"-70.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"348.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"348.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q3</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.44,-22.29C121.42,-29.04 227.25,-48.12 310.59,-80.5 314.86,-82.16 319.25,-84.22 323.44,-86.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"322.29,-89.14 331.17,-90.6 325.13,-83.92 322.29,-89.14\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.09\" y=\"-51.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"249.09\" cy=\"-171.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"249.09\" cy=\"-171.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"249.09\" y=\"-167.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M171.29,-112.22C185.4,-123.11 206.67,-139.53 223.25,-152.32\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"221.49,-154.72 230.03,-157.56 225.12,-150.01 221.49,-154.72\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.09\" y=\"-141.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"#ffaa00\" stroke-width=\"2.5\" d=\"M174.76,-100.5C208.56,-100.5 280.07,-100.5 319.52,-100.5\"/>\n",
       "<polygon fill=\"#ffaa00\" stroke=\"#ffaa00\" stroke-width=\"2.5\" points=\"319.85,-103.47 328.35,-100.5 319.85,-97.52 319.85,-103.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"249.09\" y=\"-119.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [2]</text>\n",
       "<text text-anchor=\"middle\" x=\"249.09\" y=\"-104.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q2 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M240.27,-193.7C239.31,-204 242.25,-213 249.09,-213 253.9,-213 256.79,-208.55 257.74,-202.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"260.72,-202.26 257.91,-193.7 254.77,-202.14 260.72,-202.26\"/>\n",
       "<text text-anchor=\"middle\" x=\"249.09\" y=\"-216.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M268.79,-157.81C284.74,-146.14 307.7,-129.33 324.63,-116.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"326.84,-119 331.95,-111.58 323.33,-114.2 326.84,-119\"/>\n",
       "<text text-anchor=\"middle\" x=\"300.59\" y=\"-143.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q1 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.27,-94.61C314.32,-90.01 292.32,-83.98 272.59,-81.5 251.86,-78.9 246.29,-78.72 225.59,-81.5 210.99,-83.46 195.11,-87.64 182.22,-91.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"181.03,-88.84 173.82,-94.24 182.82,-94.51 181.03,-88.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"249.09\" y=\"-85.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"447.08\" cy=\"-177.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"447.08\" cy=\"-177.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"447.08\" y=\"-173.8\" font-family=\"Times,serif\" font-size=\"14.00\">q4</text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"#ff5500\" stroke-width=\"2.5\" d=\"M363.82,-112.19C379.07,-124.3 403.17,-143.43 421.35,-157.86\"/>\n",
       "<polygon fill=\"#ff5500\" stroke=\"#ff5500\" stroke-width=\"2.5\" points=\"419.74,-160.38 428.24,-163.33 423.43,-155.72 419.74,-160.38\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.59\" y=\"-162.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [3]</text>\n",
       "<text text-anchor=\"middle\" x=\"395.59\" y=\"-147.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#ff0000\" stroke-width=\"2.5\" d=\"M427.86,-191.3C388.3,-219.47 292.68,-277.56 225.59,-236.5 187.14,-212.97 169.11,-160.71 161.34,-128.26\"/>\n",
       "<polygon fill=\"#ff0000\" stroke=\"#ff0000\" stroke-width=\"2.5\" points=\"164.17,-127.31 159.41,-119.67 158.37,-128.61 164.17,-127.31\"/>\n",
       "<text text-anchor=\"middle\" x=\"300.59\" y=\"-268.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [4]</text>\n",
       "<text text-anchor=\"middle\" x=\"300.59\" y=\"-253.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M437.94,-199.28C436.81,-209.75 439.86,-219 447.08,-219 452.17,-219 455.18,-214.43 456.13,-208.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"459.11,-207.81 456.23,-199.28 453.16,-207.74 459.11,-207.81\"/>\n",
       "<text text-anchor=\"middle\" x=\"447.08\" y=\"-222.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x11b558240>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.show_diagram(\"1001\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "blocked-snake",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Rejected]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1                →q0             1         q1\n",
    "2                 q1             0         q3\n",
    "3                 q3             0        *q4\n",
    "4                *q4             1         q1\n",
    "```\n",
    "\n",
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/dfa_1001.png?raw=true \"dfa_1001\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "adverse-profile",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Accepted]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q3</td>\n",
       "      <td>0</td>\n",
       "      <td>*q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>*q4</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>q1</td>\n",
       "      <td>1</td>\n",
       "      <td>*q2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Accepted]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1                →q0             1         q1\n",
       "2                 q1             0         q3\n",
       "3                 q3             0        *q4\n",
       "4                *q4             1         q1\n",
       "5                 q1             1        *q2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"484pt\" height=\"286pt\"\n",
       " viewBox=\"0.00 0.00 483.58 286.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 282.5)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-282.5 479.58,-282.5 479.58,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-19.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60.1\" cy=\"-19.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-15.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.78,-19.5C7.28,-19.5 19.64,-19.5 31.78,-19.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.96,-22.47 40.46,-19.5 31.96,-16.52 31.96,-22.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"155.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"155.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#ffff00\" stroke-width=\"2.5\" d=\"M75.63,-32.15C91.05,-45.59 115.57,-66.94 133.1,-82.21\"/>\n",
       "<polygon fill=\"#ffff00\" stroke=\"#ffff00\" stroke-width=\"2.5\" points=\"131.3,-84.59 139.67,-87.93 135.21,-80.1 131.3,-84.59\"/>\n",
       "<text text-anchor=\"middle\" x=\"107.6\" y=\"-85.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [1]</text>\n",
       "<text text-anchor=\"middle\" x=\"107.6\" y=\"-70.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"353.09\" cy=\"-100.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"353.09\" y=\"-96.8\" font-family=\"Times,serif\" font-size=\"14.00\">q3</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q3 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.49,-22.18C122.09,-28.77 230.39,-47.62 315.59,-80.5 319.86,-82.15 324.26,-84.2 328.45,-86.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"327.29,-89.13 336.18,-90.58 330.14,-83.9 327.29,-89.13\"/>\n",
       "<text text-anchor=\"middle\" x=\"202.59\" y=\"-51.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"254.09\" cy=\"-171.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"254.09\" cy=\"-171.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.09\" y=\"-167.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"#00ff00\" stroke-width=\"2.5\" d=\"M171.25,-111.59C186.26,-122.58 209.54,-139.62 227.43,-152.72\"/>\n",
       "<polygon fill=\"#00ff00\" stroke=\"#00ff00\" stroke-width=\"2.5\" points=\"226.12,-155.44 234.73,-158.06 229.63,-150.64 226.12,-155.44\"/>\n",
       "<text text-anchor=\"middle\" x=\"202.59\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [5]</text>\n",
       "<text text-anchor=\"middle\" x=\"202.59\" y=\"-143.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"#bfff00\" stroke-width=\"2.5\" d=\"M174.89,-100.5C209.72,-100.5 284.41,-100.5 324.81,-100.5\"/>\n",
       "<polygon fill=\"#bfff00\" stroke=\"#bfff00\" stroke-width=\"2.5\" points=\"324.85,-103.47 333.35,-100.5 324.85,-97.52 324.85,-103.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.09\" y=\"-119.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [2]</text>\n",
       "<text text-anchor=\"middle\" x=\"254.09\" y=\"-104.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q2 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M244.95,-193.28C243.82,-203.75 246.86,-213 254.09,-213 259.17,-213 262.19,-208.43 263.14,-202.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"266.12,-201.81 263.24,-193.28 260.17,-201.74 266.12,-201.81\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.09\" y=\"-216.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.79,-157.81C289.74,-146.14 312.7,-129.33 329.63,-116.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"331.84,-119 336.95,-111.58 328.33,-114.2 331.84,-119\"/>\n",
       "<text text-anchor=\"middle\" x=\"305.59\" y=\"-143.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q1 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M334.27,-94.61C319.32,-90.01 297.32,-83.98 277.59,-81.5 256.86,-78.9 251.32,-78.9 230.59,-81.5 214.25,-83.55 196.36,-88.04 182.2,-92.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"181.21,-89.33 173.92,-94.61 182.91,-95.03 181.21,-89.33\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.09\" y=\"-85.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"452.08\" cy=\"-177.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"452.08\" cy=\"-177.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"452.08\" y=\"-173.8\" font-family=\"Times,serif\" font-size=\"14.00\">q4</text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"#80ff00\" stroke-width=\"2.5\" d=\"M368.82,-112.19C384.07,-124.3 408.17,-143.43 426.35,-157.86\"/>\n",
       "<polygon fill=\"#80ff00\" stroke=\"#80ff00\" stroke-width=\"2.5\" points=\"424.74,-160.38 433.24,-163.33 428.43,-155.72 424.74,-160.38\"/>\n",
       "<text text-anchor=\"middle\" x=\"400.59\" y=\"-162.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [3]</text>\n",
       "<text text-anchor=\"middle\" x=\"400.59\" y=\"-147.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#40ff00\" stroke-width=\"2.5\" d=\"M432.78,-191.15C393.45,-218.68 298.91,-275.08 230.59,-236.5 190.52,-213.87 170.75,-160.83 162.03,-128.08\"/>\n",
       "<polygon fill=\"#40ff00\" stroke=\"#40ff00\" stroke-width=\"2.5\" points=\"164.81,-126.94 159.86,-119.42 159.04,-128.39 164.81,-126.94\"/>\n",
       "<text text-anchor=\"middle\" x=\"305.59\" y=\"-267.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [4]</text>\n",
       "<text text-anchor=\"middle\" x=\"305.59\" y=\"-252.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M442.94,-199.28C441.81,-209.75 444.86,-219 452.08,-219 457.17,-219 460.18,-214.43 461.13,-208.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"464.11,-207.81 461.23,-199.28 458.16,-207.74 464.11,-207.81\"/>\n",
       "<text text-anchor=\"middle\" x=\"452.08\" y=\"-222.8\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x11b558748>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfa.show_diagram(\"10011\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "blind-montana",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Accepted]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1                →q0             1         q1\n",
    "2                 q1             0         q3\n",
    "3                 q3             0        *q4\n",
    "4                *q4             1         q1\n",
    "5                 q1             1        *q2\n",
    "```\n",
    "\n",
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/dfa_10011.png?raw=true \"dfa_10011\")\n",
    "\n",
    "### VisualNFA\n",
    "\n",
    "#### Importing\n",
    "\n",
    "Import needed classes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "eligible-socket",
   "metadata": {},
   "outputs": [],
   "source": [
    "from automata.fa.nfa import NFA\n",
    "\n",
    "from visual_automata.fa.nfa import VisualNFA"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "substantial-contact",
   "metadata": {},
   "source": [
    "#### Instantiating NFAs\n",
    "\n",
    "Define an visual_automata NFA that can accept any string with the pattern 10, 1010, 101010."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "extraordinary-stupid",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa = VisualNFA(\n",
    "    states={\"q0\", \"q1\", \"q2\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\"\": {\"q2\"}, \"1\": {\"q1\"}},\n",
    "        \"q1\": {\"1\": {\"q2\"}, \"0\": {\"q0\", \"q2\"}},\n",
    "        \"q2\": {},\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"q0\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "medieval-mandate",
   "metadata": {},
   "source": [
    "#### Converting\n",
    "\n",
    "An automata-lib NFA can be converted to a VisualNFA.\n",
    "\n",
    "Define an automata-lib NFA that can accept any string with the pattern 10, 1010, 101010."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "related-milan",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa = NFA(\n",
    "    states={\"q0\", \"q1\", \"q2\"},\n",
    "    input_symbols={\"0\", \"1\"},\n",
    "    transitions={\n",
    "        \"q0\": {\"\": {\"q2\"}, \"1\": {\"q1\"}},\n",
    "        \"q1\": {\"1\": {\"q2\"}, \"0\": {\"q0\", \"q2\"}},\n",
    "        \"q2\": {},\n",
    "    },\n",
    "    initial_state=\"q0\",\n",
    "    final_states={\"q0\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spatial-sunday",
   "metadata": {},
   "source": [
    "Convert automata-lib NFA to VisualNFA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "cheap-impossible",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa = VisualNFA(nfa)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "jewish-defensive",
   "metadata": {},
   "source": [
    "#### Transition Table\n",
    "\n",
    "Outputs the transition table for the given DFA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "terminal-helena",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>λ</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→*q0</th>\n",
       "      <td>∅</td>\n",
       "      <td>q1</td>\n",
       "      <td>q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q1</th>\n",
       "      <td>{*q0,q2}</td>\n",
       "      <td>q2</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q2</th>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             0   1   λ\n",
       "→*q0         ∅  q1  q2\n",
       "q1    {*q0,q2}  q2   ∅\n",
       "q2           ∅   ∅   ∅"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "relevant-athletics",
   "metadata": {},
   "source": [
    "```text\n",
    "             0   1   λ\n",
    "→*q0         ∅  q1  q2\n",
    "q1    {*q0,q2}  q2   ∅\n",
    "q2           ∅   ∅   ∅\n",
    "```\n",
    "\n",
    "#### Eliminate lambda/epsilon\n",
    "\n",
    "Creates a NFA with lambda transitions removed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "dirty-texture",
   "metadata": {},
   "outputs": [],
   "source": [
    "nfa_eliminated = VisualNFA.eliminate_lambda(nfa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "wrong-shore",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→*q0</th>\n",
       "      <td>∅</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q1</th>\n",
       "      <td>{*q0,q2}</td>\n",
       "      <td>q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q2</th>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             0   1\n",
       "→*q0         ∅  q1\n",
       "q1    {*q0,q2}  q2\n",
       "q2           ∅   ∅"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa_eliminated.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "important-cheat",
   "metadata": {},
   "source": [
    "```text\n",
    "             0   1\n",
    "→*q0         ∅  q1\n",
    "q1    {*q0,q2}  q2\n",
    "q2           ∅   ∅\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "herbal-marathon",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"276pt\" height=\"55pt\"\n",
       " viewBox=\"0.00 0.00 275.59 55.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 51)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-51 271.59,-51 271.59,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-23.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"64.1\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.85,-23.5C7.37,-23.5 19.27,-23.5 31.49,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.82,-26.47 40.32,-23.5 31.82,-20.52 31.82,-26.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"158.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"158.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M87.84,-23.5C100.46,-23.5 116.26,-23.5 129.57,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.83,-26.47 138.33,-23.5 129.83,-20.52 129.83,-26.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.1\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.41,-13.23C135.19,-9.73 127.81,-6.26 120.6,-4.5 111.21,-2.2 101.15,-4.22 92.21,-7.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"90.92,-4.99 84.36,-11.16 93.34,-10.42 90.92,-4.99\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.1\" y=\"-8.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"248.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"248.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M177.76,-23.5C190.01,-23.5 206.23,-23.5 219.91,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.96,-26.47 228.46,-23.5 219.96,-20.52 219.96,-26.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.58,-12.6C184.66,-6.81 198.19,-1.46 210.59,-4.5 214.99,-5.57 219.45,-7.28 223.67,-9.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"222.48,-11.98 231.4,-13.23 225.21,-6.69 222.48,-11.98\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-8.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x121fe3e10>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa_eliminated.show_diagram()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "handmade-transcription",
   "metadata": {},
   "source": [
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/eliminated_nfa.png?raw=true \"eliminated_nfa\")\n",
    "\n",
    "#### Check input strings\n",
    "\n",
    "`101` does not correspond with the pattern `10`, `1010`, `101010`, and is therefore `Rejected`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "together-talent",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Rejected]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q2</td>\n",
       "      <td>1</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Rejected]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1               →*q0             1         q1\n",
       "2                 q1             0         q2\n",
       "3                 q2             1          ∅"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.input_check(\"101\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "divine-thesis",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Rejected]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1               →*q0             1         q1\n",
    "2                 q1             0         q2\n",
    "3                 q2             1          ∅\n",
    "```\n",
    "\n",
    "`1010` does correspond with the pattern `10`, `1010`, `101010`, and is therefore `Accepted`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "light-april",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Accepted]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>→*q0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>→*q0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Accepted]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1               →*q0             1         q1\n",
       "2                 q1             0       →*q0\n",
       "3               →*q0             1         q1\n",
       "4                 q1             0       →*q0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.input_check(\"1010\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "coral-positive",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Accepted]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1               →*q0             1         q1\n",
    "2                 q1             0       →*q0\n",
    "3               →*q0             1         q1\n",
    "4                 q1             0       →*q0\n",
    "```\n",
    "\n",
    "#### Show Diagram\n",
    "\n",
    "For IPython `nfa.show_diagram()` may be used.\\\n",
    "For a python script `nfa.show_diagram(view=True)` may be used to automatically view the graph as a PDF file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "identical-worship",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"276pt\" height=\"79pt\"\n",
       " viewBox=\"0.00 0.00 275.59 79.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 75)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-75 271.59,-75 271.59,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-23.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"64.1\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.85,-23.5C7.37,-23.5 19.27,-23.5 31.49,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.82,-26.47 40.32,-23.5 31.82,-20.52 31.82,-26.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"158.09\" cy=\"-51.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"158.09\" y=\"-47.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M85.91,-32.4C92.17,-34.89 99.1,-37.47 105.6,-39.5 113.58,-41.99 122.4,-44.23 130.45,-46.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.86,-48.99 138.81,-47.92 131.15,-43.18 129.86,-48.99\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.1\" y=\"-46.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"248.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"248.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M87.3,-17.63C93.22,-16.17 99.63,-14.68 105.6,-13.5 151.37,-4.4 164.94,-3.82 210.59,-13.5 213.9,-14.2 217.35,-15.02 220.75,-15.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.02,-18.77 229,-18.09 221.56,-13.02 220.02,-18.77\"/>\n",
       "<text text-anchor=\"middle\" x=\"158.09\" y=\"-11.3\" font-family=\"Times,serif\" font-size=\"14.00\"> λ </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M144.74,-37.13C138.28,-30.73 129.8,-23.88 120.6,-20.5 112.81,-17.64 104,-17.04 95.73,-17.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"95.21,-14.56 87.04,-18.36 95.8,-20.48 95.21,-14.56\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.1\" y=\"-24.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M177.43,-48.08C187.37,-46.02 199.79,-43.09 210.59,-39.5 214.39,-38.24 218.33,-36.73 222.16,-35.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"223.64,-37.75 230.26,-31.65 221.28,-32.29 223.64,-37.75\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-47.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M171.45,-37.13C177.91,-30.73 186.38,-23.88 195.59,-20.5 203.37,-17.64 212.26,-17.24 220.43,-17.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.13,-20.86 228.93,-18.95 220.87,-14.95 220.13,-20.86\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.09\" y=\"-24.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x122198320>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.show_diagram()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "nutritional-bedroom",
   "metadata": {},
   "source": [
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/nfa.png?raw=true \"nfa\")\n",
    "\n",
    "The `show_diagram` method also accepts input strings, and will return a graph with gradient `red` arrows for `Rejected` results, and gradient `green` arrows for `Accepted` results. It will also display a table with transitions states stepwise. The steps in this table will correspond with the `[number]` over each traversed arrow.\n",
    "\n",
    "Please note that for visual purposes additional arrows are added if a transition is traversed more than once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "supported-think",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Rejected]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>q2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q2</td>\n",
       "      <td>1</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Rejected]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1               →*q0             1         q1\n",
       "2                 q1             0         q2\n",
       "3                 q2             1          ∅"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"378pt\" height=\"82pt\"\n",
       " viewBox=\"0.00 0.00 377.59 82.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 78.5)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-78.5 373.59,-78.5 373.59,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-23.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-23.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"64.1\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.85,-23.5C7.37,-23.5 19.27,-23.5 31.49,-23.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.82,-26.47 40.32,-23.5 31.82,-20.52 31.82,-26.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"163.09\" cy=\"-51.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.09\" y=\"-47.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#ffff00\" stroke-width=\"2.5\" d=\"M85.88,-32.48C92.14,-34.97 99.08,-37.53 105.6,-39.5 115.13,-42.37 125.76,-44.82 135.21,-46.74\"/>\n",
       "<polygon fill=\"#ffff00\" stroke=\"#ffff00\" stroke-width=\"2.5\" points=\"134.92,-49.72 143.83,-48.42 136.06,-43.88 134.92,-49.72\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-63.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [1]</text>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-48.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"258.09\" cy=\"-23.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"258.09\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M86.81,-16.91C92.85,-15.27 99.44,-13.65 105.6,-12.5 155.83,-3.09 170.49,-2.4 220.59,-12.5 224,-13.18 227.54,-14.05 231.03,-15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"230.45,-17.93 239.44,-17.45 232.11,-12.21 230.45,-17.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.09\" y=\"-9.3\" font-family=\"Times,serif\" font-size=\"14.00\"> λ </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.74,-37.13C143.28,-30.73 134.8,-23.88 125.6,-20.5 116.3,-17.08 105.66,-16.59 95.92,-17.32\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"95.4,-14.39 87.29,-18.3 96.07,-20.3 95.4,-14.39\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-24.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"#ff8000\" stroke-width=\"2.5\" d=\"M182.41,-48.59C193.59,-46.57 208.09,-43.52 220.59,-39.5 224.4,-38.27 228.35,-36.79 232.18,-35.22\"/>\n",
       "<polygon fill=\"#ff8000\" stroke=\"#ff8000\" stroke-width=\"2.5\" points=\"233.66,-37.82 240.29,-31.72 231.3,-32.36 233.66,-37.82\"/>\n",
       "<text text-anchor=\"middle\" x=\"210.59\" y=\"-63.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [2]</text>\n",
       "<text text-anchor=\"middle\" x=\"210.59\" y=\"-48.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.45,-37.13C182.91,-30.73 191.38,-23.88 200.59,-20.5 209.98,-17.05 220.84,-16.82 230.51,-17.79\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"230.16,-20.75 238.99,-18.97 230.98,-14.85 230.16,-20.75\"/>\n",
       "<text text-anchor=\"middle\" x=\"210.59\" y=\"-24.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- Ø -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>Ø</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"351.59\" cy=\"-23.5\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"351.59\" y=\"-19.8\" font-family=\"Times,serif\" font-size=\"14.00\">Ø</text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;Ø -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q2&#45;&gt;Ø</title>\n",
       "<path fill=\"none\" stroke=\"#ff0000\" stroke-width=\"2.5\" d=\"M277.61,-23.5C291.1,-23.5 309.56,-23.5 324.54,-23.5\"/>\n",
       "<polygon fill=\"#ff0000\" stroke=\"#ff0000\" stroke-width=\"2.5\" points=\"324.84,-26.47 333.34,-23.5 324.84,-20.52 324.84,-26.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"305.59\" y=\"-42.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [3]</text>\n",
       "<text text-anchor=\"middle\" x=\"305.59\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x122132978>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.show_diagram(\"101\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "provincial-vietnamese",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Rejected]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1               →*q0             1         q1\n",
    "2                 q1             0         q2\n",
    "3                 q2             1          ∅\n",
    "```\n",
    "\n",
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/nfa_101.png?raw=true \"nfa_101\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "healthy-basketball",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Accepted]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>→*q0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>→*q0</td>\n",
       "      <td>1</td>\n",
       "      <td>q1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>q1</td>\n",
       "      <td>0</td>\n",
       "      <td>→*q0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Accepted]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1               →*q0             1         q1\n",
       "2                 q1             0       →*q0\n",
       "3               →*q0             1         q1\n",
       "4                 q1             0       →*q0"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"281pt\" height=\"182pt\"\n",
       " viewBox=\"0.00 0.00 280.59 182.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 178.5)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-178.5 276.59,-178.5 276.59,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-57.5\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-57.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"64.1\" cy=\"-57.5\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"64.1\" y=\"-53.8\" font-family=\"Times,serif\" font-size=\"14.00\">q0</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.85,-57.5C7.37,-57.5 19.27,-57.5 31.49,-57.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.82,-60.47 40.32,-57.5 31.82,-54.52 31.82,-60.47\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"163.09\" cy=\"-57.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.09\" y=\"-53.8\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#ffff00\" stroke-width=\"2.5\" d=\"M70.85,-80.26C79.73,-110.77 98.62,-159.19 125.6,-141.5 144.39,-129.17 153.56,-104.85 158,-85.53\"/>\n",
       "<polygon fill=\"#ffff00\" stroke=\"#ffff00\" stroke-width=\"2.5\" points=\"160.94,-86 159.72,-77.07 155.11,-84.81 160.94,-86\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-163.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [1]</text>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-148.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"#55ff00\" stroke-width=\"2.5\" d=\"M81.36,-73.85C88.24,-79.65 96.71,-85.49 105.6,-88.5 114.02,-91.35 117.25,-91.56 125.6,-88.5 131.93,-86.17 137.91,-82.21 143.13,-77.88\"/>\n",
       "<polygon fill=\"#55ff00\" stroke=\"#55ff00\" stroke-width=\"2.5\" points=\"145.46,-79.78 149.74,-71.86 141.45,-75.38 145.46,-79.78\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-109.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [3]</text>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-94.3\" font-family=\"Times,serif\" font-size=\"14.00\">1 </text>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"253.09\" cy=\"-19.5\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"253.09\" y=\"-15.8\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q0&#45;&gt;q2 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q0&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.76,-38.54C85.78,-30.3 95.09,-21.42 105.6,-16.5 149.99,4.28 167.1,-1.35 215.59,-8.5 219.03,-9 222.59,-9.77 226.08,-10.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"225.52,-13.59 234.51,-13.06 227.15,-7.87 225.52,-13.59\"/>\n",
       "<text text-anchor=\"middle\" x=\"163.09\" y=\"-7.3\" font-family=\"Times,serif\" font-size=\"14.00\"> λ </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#aaff00\" stroke-width=\"2.5\" d=\"M143.5,-57.5C130.3,-57.5 112.27,-57.5 96.82,-57.5\"/>\n",
       "<polygon fill=\"#aaff00\" stroke=\"#aaff00\" stroke-width=\"2.5\" points=\"96.59,-54.52 88.09,-57.5 96.59,-60.47 96.59,-54.52\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-76.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [2]</text>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-61.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q0 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q0</title>\n",
       "<path fill=\"none\" stroke=\"#00ff00\" stroke-width=\"2.5\" d=\"M150.64,-42.48C144.18,-35.27 135.43,-27.37 125.6,-23.5 117.33,-20.24 113.95,-20.46 105.6,-23.5 98.92,-25.93 92.59,-29.99 86.99,-34.48\"/>\n",
       "<polygon fill=\"#00ff00\" stroke=\"#00ff00\" stroke-width=\"2.5\" points=\"84.77,-32.47 80.33,-40.31 88.69,-36.95 84.77,-32.47\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-42.3\" font-family=\"Times,serif\" font-size=\"14.00\"> [4]</text>\n",
       "<text text-anchor=\"middle\" x=\"115.6\" y=\"-27.3\" font-family=\"Times,serif\" font-size=\"14.00\">0 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M181.28,-50.21C191.3,-45.94 204.17,-40.44 215.59,-35.5 219.26,-33.91 223.14,-32.22 226.94,-30.56\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"228.43,-33.16 235.02,-27.02 226.04,-27.71 228.43,-33.16\"/>\n",
       "<text text-anchor=\"middle\" x=\"208.09\" y=\"-45.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 1 </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174,-40.74C180.34,-31.74 189.46,-21.49 200.59,-16.5 208.27,-13.05 217.26,-12.54 225.55,-13.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"225.36,-16.25 234.19,-14.48 226.18,-10.36 225.36,-16.25\"/>\n",
       "<text text-anchor=\"middle\" x=\"208.09\" y=\"-20.3\" font-family=\"Times,serif\" font-size=\"14.00\"> 0 </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x121ccd9b0>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nfa.show_diagram(\"1010\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "russian-hypothesis",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Accepted]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1               →*q0             1         q1\n",
    "2                 q1             0       →*q0\n",
    "3               →*q0             1         q1\n",
    "4                 q1             0       →*q0\n",
    "```\n",
    "\n",
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/nfa_1010.png?raw=true \"nfa_1010\")\n",
    "\n",
    "Please note that for long input strings, the path calculations may take some time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "varying-governor",
   "metadata": {},
   "outputs": [],
   "source": [
    "big_nfa = VisualNFA(\n",
    "    states={\"q1\", \"q2\", \"q3\", \"q4\", \"q5\", \"q6\", \"q7\", \"q8\"},\n",
    "    input_symbols={\"A\", \"C\", \"G\", \"T\"},\n",
    "    transitions={\n",
    "        \"q1\": {\"A\": {\"q7\"}, \"C\": {\"q4\"}, \"G\": {\"q4\", \"q2\"}, \"T\": {\"q4\"}},\n",
    "        \"q2\": {\"A\": {\"q3\", \"q6\"}, \"C\": {\"q2\", \"q4\"}, \"G\": {\"q3\", \"q6\"}, \"T\": {\"q6\"}},\n",
    "        \"q3\": {\"A\": {\"q8\"}, \"C\": {\"q8\"}, \"T\": {\"q8\"}},\n",
    "        \"q4\": {\"A\": {\"q5\"}, \"C\": {\"q4\"}, \"G\": {\"q5\"}, \"T\": {\"q2\", \"q4\", \"q5\"}},\n",
    "        \"q5\": {\"A\": {\"q3\", \"q8\"}, \"C\": {\"q3\", \"q8\"}, \"G\": {\"q8\"}, \"T\": {\"q3\", \"q8\"}},\n",
    "        \"q6\": {\"A\": {\"q8\"}, \"C\": {\"q8\"}, \"G\": {\"q8\"}, \"T\": {\"q8\"}},\n",
    "        \"q7\": {\"A\": {\"q7\", \"q8\"}, \"C\": {\"q7\", \"q8\"}, \"G\": {\"q8\"}, \"T\": {\"q3\", \"q8\"}},\n",
    "        \"q8\": {},\n",
    "    },\n",
    "    initial_state=\"q1\",\n",
    "    final_states={\"q8\"},\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "freelance-delivery",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>A</th>\n",
       "      <th>C</th>\n",
       "      <th>G</th>\n",
       "      <th>T</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>→q1</th>\n",
       "      <td>q7</td>\n",
       "      <td>q4</td>\n",
       "      <td>{q2,q4}</td>\n",
       "      <td>q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q2</th>\n",
       "      <td>{q3,q6}</td>\n",
       "      <td>{q2,q4}</td>\n",
       "      <td>{q3,q6}</td>\n",
       "      <td>q6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q3</th>\n",
       "      <td>*q8</td>\n",
       "      <td>*q8</td>\n",
       "      <td>∅</td>\n",
       "      <td>*q8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q4</th>\n",
       "      <td>q5</td>\n",
       "      <td>q4</td>\n",
       "      <td>q5</td>\n",
       "      <td>{q2,q4,q5}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q5</th>\n",
       "      <td>{q3,*q8}</td>\n",
       "      <td>{q3,*q8}</td>\n",
       "      <td>*q8</td>\n",
       "      <td>{q3,*q8}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q6</th>\n",
       "      <td>*q8</td>\n",
       "      <td>*q8</td>\n",
       "      <td>*q8</td>\n",
       "      <td>*q8</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>q7</th>\n",
       "      <td>{q7,*q8}</td>\n",
       "      <td>{q7,*q8}</td>\n",
       "      <td>*q8</td>\n",
       "      <td>{q3,*q8}</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>*q8</th>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "      <td>∅</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            A         C        G           T\n",
       "→q1        q7        q4  {q2,q4}          q4\n",
       "q2    {q3,q6}   {q2,q4}  {q3,q6}          q6\n",
       "q3        *q8       *q8        ∅         *q8\n",
       "q4         q5        q4       q5  {q2,q4,q5}\n",
       "q5   {q3,*q8}  {q3,*q8}      *q8    {q3,*q8}\n",
       "q6        *q8       *q8      *q8         *q8\n",
       "q7   {q7,*q8}  {q7,*q8}      *q8    {q3,*q8}\n",
       "*q8         ∅         ∅        ∅           ∅"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "big_nfa.table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "capable-oxide",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead tr th {\n",
       "        text-align: left;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th colspan=\"3\" halign=\"left\">[Accepted]</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Step:</th>\n",
       "      <th>Current state:</th>\n",
       "      <th>Input symbol:</th>\n",
       "      <th>New state:</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>→q1</td>\n",
       "      <td>C</td>\n",
       "      <td>q4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>q4</td>\n",
       "      <td>G</td>\n",
       "      <td>q5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>q5</td>\n",
       "      <td>C</td>\n",
       "      <td>*q8</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          [Accepted]                         \n",
       "Step: Current state: Input symbol: New state:\n",
       "1                →q1             C         q4\n",
       "2                 q4             G         q5\n",
       "3                 q5             C        *q8"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.46.1 (20210213.1702)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"534pt\" height=\"576pt\"\n",
       " viewBox=\"0.00 0.00 534.49 576.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.95 0.95) rotate(0) translate(4 600.12)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-600.12 556.58,-600.12 556.58,4 -4,4\"/>\n",
       "<!-- Initial -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Initial</title>\n",
       "<ellipse fill=\"black\" stroke=\"black\" cx=\"1.8\" cy=\"-265.12\" rx=\"1.8\" ry=\"1.8\"/>\n",
       "</g>\n",
       "<!-- q1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>q1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"60.1\" cy=\"-265.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"60.1\" y=\"-261.42\" font-family=\"Times,serif\" font-size=\"14.00\">q1</text>\n",
       "</g>\n",
       "<!-- Initial&#45;&gt;q1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>Initial&#45;&gt;q1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3.78,-265.12C7.28,-265.12 19.64,-265.12 31.78,-265.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"31.96,-268.09 40.46,-265.12 31.96,-262.14 31.96,-268.09\"/>\n",
       "</g>\n",
       "<!-- q2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>q2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"153.09\" cy=\"-436.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-432.42\" font-family=\"Times,serif\" font-size=\"14.00\">q2</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q2 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M70.16,-282.14C86.3,-312.48 120.12,-376.04 138.87,-411.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"136.45,-413.06 143.07,-419.17 141.71,-410.26 136.45,-413.06\"/>\n",
       "<text text-anchor=\"middle\" x=\"106.6\" y=\"-369.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>q4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"245.09\" cy=\"-302.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"245.09\" y=\"-298.42\" font-family=\"Times,serif\" font-size=\"14.00\">q4</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"#ffff00\" stroke-width=\"2.5\" d=\"M78.3,-272.57C84.32,-274.95 91.17,-277.4 97.6,-279.12 138.4,-290.01 187.06,-296.39 216.75,-299.56\"/>\n",
       "<polygon fill=\"#ffff00\" stroke=\"#ffff00\" stroke-width=\"2.5\" points=\"216.57,-302.54 225.33,-300.45 217.18,-296.62 216.57,-302.54\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-312.92\" font-family=\"Times,serif\" font-size=\"14.00\"> [1]</text>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-297.92\" font-family=\"Times,serif\" font-size=\"14.00\">C </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76.16,-254.01C97.5,-239.67 137.81,-217.71 172.59,-228.12 197.9,-235.69 217.83,-259.2 230.15,-277.72\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"227.88,-279.71 234.95,-285.29 232.91,-276.52 227.88,-279.71\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-231.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M79.55,-263.58C101.91,-262.22 140.56,-261.48 172.59,-269.12 189.38,-273.12 206.99,-281.2 220.54,-288.36\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.12,-290.98 228.01,-292.43 221.97,-285.75 219.12,-290.98\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-272.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>q7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"340.09\" cy=\"-46.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"340.09\" y=\"-42.42\" font-family=\"Times,serif\" font-size=\"14.00\">q7</text>\n",
       "</g>\n",
       "<!-- q1&#45;&gt;q7 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>q1&#45;&gt;q7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M74.62,-251.44C81.36,-244.82 89.73,-236.85 97.6,-230.12 175.02,-163.87 273.22,-92.75 316.67,-61.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"318.43,-64.29 323.64,-56.95 314.99,-59.44 318.43,-64.29\"/>\n",
       "<text text-anchor=\"middle\" x=\"199.09\" y=\"-157.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q2 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M145.24,-454.25C143.77,-464.33 146.39,-473.62 153.09,-473.62 157.81,-473.62 160.5,-469.03 161.18,-462.8\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"164.15,-462.67 160.95,-454.25 158.2,-462.83 164.15,-462.67\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.09\" y=\"-477.42\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>q3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"432.08\" cy=\"-362.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-358.42\" font-family=\"Times,serif\" font-size=\"14.00\">q3</text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M172.75,-433.49C228.81,-425.57 392.11,-402.41 394.59,-401.12 402.19,-397.14 409.07,-390.95 414.75,-384.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"417.24,-386.31 420.42,-377.89 412.68,-382.49 417.24,-386.31\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-421.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q3 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M172.31,-440.23C215.22,-448.84 324.34,-464.27 394.59,-417.12 405.38,-409.87 413.78,-398.24 419.78,-387.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"422.43,-388.9 423.73,-379.99 417.15,-386.15 422.43,-388.9\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-453.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.39,-417.47C165.15,-399.19 175.6,-371.1 190.59,-350.12 199.2,-338.07 211.32,-326.89 221.84,-318.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"223.96,-320.46 228.81,-312.88 220.29,-315.78 223.96,-320.46\"/>\n",
       "<text text-anchor=\"middle\" x=\"199.09\" y=\"-353.92\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>q6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"432.08\" cy=\"-493.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-489.42\" font-family=\"Times,serif\" font-size=\"14.00\">q6</text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q6 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M154.3,-455.73C155.74,-481.08 162.47,-524.41 190.59,-545.12 263.6,-598.88 314.6,-587.81 394.59,-545.12 405.44,-539.32 413.77,-528.7 419.71,-518.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"422.37,-519.89 423.79,-510.99 417.13,-517.07 422.37,-519.89\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-584.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q6 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M158.15,-455.23C162.84,-472.1 172.38,-495.73 190.59,-507.12 258.36,-549.5 358.97,-520.8 405.62,-503.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"406.8,-506.26 413.68,-500.46 404.68,-500.7 406.8,-506.26\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-531.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q2&#45;&gt;q6 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>q2&#45;&gt;q6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M166.12,-450.64C172.62,-457.45 181.22,-464.96 190.59,-469.12 262.52,-501 358.09,-499.06 404.09,-495.73\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"404.37,-498.69 412.61,-495.06 403.9,-492.76 404.37,-498.69\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-497.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>q8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"529.08\" cy=\"-267.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"529.08\" cy=\"-267.12\" rx=\"23.5\" ry=\"23.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"529.08\" y=\"-263.42\" font-family=\"Times,serif\" font-size=\"14.00\">q8</text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q8 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M440.67,-344.48C446.97,-331.34 456.94,-313.6 469.58,-301.12 478.18,-292.63 489.3,-285.48 499.54,-279.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"500.93,-282.59 507.14,-276.06 498.22,-277.29 500.93,-282.59\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-304.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q8 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M451.67,-363.62C463.07,-363.58 477.38,-361.72 487.58,-354.12 505.42,-340.82 515.67,-317.72 521.39,-298.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"524.32,-299.23 523.71,-290.24 518.59,-297.65 524.32,-299.23\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-365.92\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q3&#45;&gt;q8 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>q3&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M448.05,-350.68C459.37,-341.76 475.04,-328.79 487.58,-316.12 494.83,-308.79 502.19,-300.29 508.6,-292.44\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"511.19,-293.96 514.19,-285.47 506.55,-290.24 511.19,-293.96\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-336.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q2 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M235.02,-319.03C227.94,-331.91 217.65,-349.95 207.59,-365.12 204.28,-370.11 185.33,-395.14 170.91,-414.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"168.44,-412.42 165.65,-420.98 173.17,-416.02 168.44,-412.42\"/>\n",
       "<text text-anchor=\"middle\" x=\"199.09\" y=\"-391.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q4 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M241.09,-321.41C240.53,-331.03 241.87,-339.62 245.09,-339.62 247.26,-339.62 248.57,-335.74 249.03,-330.28\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"252.01,-329.93 249.09,-321.41 246.06,-329.89 252.01,-329.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"245.09\" y=\"-343.42\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q4 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M238.48,-320.59C234.94,-338.29 237.14,-357.62 245.09,-357.62 251.74,-357.62 254.37,-344.11 252.98,-329.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"255.88,-328.58 251.71,-320.59 249.99,-329.44 255.88,-328.58\"/>\n",
       "<text text-anchor=\"middle\" x=\"245.09\" y=\"-361.42\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>q5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"340.09\" cy=\"-294.12\" rx=\"19.5\" ry=\"19.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"340.09\" y=\"-290.42\" font-family=\"Times,serif\" font-size=\"14.00\">q5</text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q5 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q5</title>\n",
       "<path fill=\"none\" stroke=\"#80ff00\" stroke-width=\"2.5\" d=\"M263.5,-308.83C274.72,-312.27 289.59,-315.15 302.59,-312.12 306.76,-311.15 310.99,-309.63 315.04,-307.87\"/>\n",
       "<polygon fill=\"#80ff00\" stroke=\"#80ff00\" stroke-width=\"2.5\" points=\"316.61,-310.42 322.97,-304.05 314.03,-305.06 316.61,-310.42\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-332.92\" font-family=\"Times,serif\" font-size=\"14.00\"> [2]</text>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-317.92\" font-family=\"Times,serif\" font-size=\"14.00\">G </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q5 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M264.12,-296.76C269.96,-295.27 276.5,-293.86 282.59,-293.12 292.11,-291.96 302.6,-291.83 311.93,-292.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"311.82,-295.09 320.45,-292.5 312.09,-289.15 311.82,-295.09\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-296.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q4&#45;&gt;q5 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>q4&#45;&gt;q5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M258.95,-288.36C265.4,-282.45 273.73,-276.21 282.59,-273.12 293.77,-269.22 306.1,-272.87 316.39,-278.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"314.95,-280.76 323.8,-282.42 317.92,-275.6 314.95,-280.76\"/>\n",
       "<text text-anchor=\"middle\" x=\"292.59\" y=\"-276.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q3 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M343.46,-313.69C347.04,-333.74 355.91,-363.9 377.59,-378.12 386.67,-384.07 398.05,-381.75 407.98,-377.26\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.4,-379.87 415.55,-373.3 406.64,-374.6 409.4,-379.87\"/>\n",
       "<text text-anchor=\"middle\" x=\"386.09\" y=\"-385.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q3 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M350.91,-310.34C357.47,-320.05 366.83,-332.03 377.59,-340.12 385.7,-346.22 395.74,-350.93 404.93,-354.4\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"404.04,-357.24 413.04,-357.24 406,-351.63 404.04,-357.24\"/>\n",
       "<text text-anchor=\"middle\" x=\"386.09\" y=\"-353.92\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q3 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.43,-300.88C369.39,-305.62 383.53,-312.62 394.59,-321.12 401.58,-326.49 408.28,-333.34 414,-339.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"412.04,-342.19 419.77,-346.8 416.6,-338.37 412.04,-342.19\"/>\n",
       "<text text-anchor=\"middle\" x=\"386.09\" y=\"-324.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"#00ff00\" stroke-width=\"2.5\" d=\"M342.33,-274.49C345.89,-237.78 359.65,-160.33 412.59,-137.12 446.81,-122.11 466.9,-144 487.58,-175.12 500.31,-194.28 510.67,-218.1 517.72,-236.7\"/>\n",
       "<polygon fill=\"#00ff00\" stroke=\"#00ff00\" stroke-width=\"2.5\" points=\"515,-237.9 520.73,-244.84 520.58,-235.84 515,-237.9\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-155.92\" font-family=\"Times,serif\" font-size=\"14.00\"> [3]</text>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-140.92\" font-family=\"Times,serif\" font-size=\"14.00\">C </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q8 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M359.7,-291.43C391.69,-286.81 457.41,-277.32 496.62,-271.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"497.52,-274.54 505.51,-270.38 496.67,-268.65 497.52,-274.54\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-287.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q8 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M348.34,-276.15C354.25,-264.12 363.89,-249.24 377.59,-242.12 416.63,-221.82 468.39,-238.4 499.91,-252.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"498.89,-255.35 507.85,-256.24 501.4,-249.96 498.89,-255.35\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-239.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q5&#45;&gt;q8 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>q5&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M348.3,-276.27C354.46,-262.79 364.42,-244.55 377.59,-232.12 390.3,-220.11 395.59,-218.23 412.59,-214.12 429.43,-210.04 434.99,-209.1 451.58,-214.12 469.99,-219.69 471.76,-227.19 487.58,-238.12 492.46,-241.49 497.63,-245.13 502.58,-248.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"500.98,-251.18 509.62,-253.7 504.45,-246.34 500.98,-251.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-217.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q8 -->\n",
       "<g id=\"edge30\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M451.46,-489.26C463.52,-485.76 478.66,-479.38 487.58,-468.12 508.01,-442.32 520.06,-348.93 525.17,-299.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"528.14,-299.31 526.02,-290.56 522.21,-298.72 528.14,-299.31\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-484.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q8 -->\n",
       "<g id=\"edge31\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M445.01,-478.25C452.03,-469.62 461.15,-458.62 469.58,-449.12 477.3,-440.41 482,-440.32 487.58,-430.12 510.46,-388.33 520.64,-333.48 525,-299.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"527.98,-299.41 526.04,-290.61 522.07,-298.7 527.98,-299.41\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-452.92\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q8 -->\n",
       "<g id=\"edge32\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M440.31,-475.23C447.27,-458.42 458.37,-432.68 469.58,-411.12 476.76,-397.32 480.95,-395.18 487.58,-381.12 500.51,-353.71 511.73,-320.99 519.06,-297.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"521.91,-298.49 521.58,-289.49 516.23,-296.74 521.91,-298.49\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-414.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q6&#45;&gt;q8 -->\n",
       "<g id=\"edge33\" class=\"edge\">\n",
       "<title>q6&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M449.97,-501.33C461.8,-505.77 477.29,-508.78 487.58,-500.12 517.63,-474.84 525.39,-357.27 527.39,-299.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"530.37,-299.27 527.66,-290.68 524.42,-299.08 530.37,-299.27\"/>\n",
       "<text text-anchor=\"middle\" x=\"478.58\" y=\"-508.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q3 -->\n",
       "<g id=\"edge39\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M345.63,-64.82C356.27,-108.23 384.1,-219.03 412.59,-310.12 415.22,-318.53 418.35,-327.62 421.28,-335.81\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"418.54,-336.97 424.23,-343.94 424.13,-334.94 418.54,-336.97\"/>\n",
       "<text text-anchor=\"middle\" x=\"386.09\" y=\"-249.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q7 -->\n",
       "<g id=\"edge34\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M336.08,-65.41C335.53,-75.03 336.87,-83.62 340.09,-83.62 342.25,-83.62 343.57,-79.74 344.03,-74.28\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"347,-73.93 344.09,-65.41 341.05,-73.89 347,-73.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"340.09\" y=\"-87.42\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q7 -->\n",
       "<g id=\"edge36\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M333.47,-64.59C329.93,-82.29 332.14,-101.62 340.09,-101.62 346.73,-101.62 349.36,-88.11 347.98,-73.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"350.87,-72.58 346.7,-64.59 344.99,-73.44 350.87,-72.58\"/>\n",
       "<text text-anchor=\"middle\" x=\"340.09\" y=\"-105.42\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q8 -->\n",
       "<g id=\"edge35\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.44,-52.87C389.79,-66.05 455.59,-98.32 487.58,-148.12 504.99,-175.22 515.79,-210.63 521.81,-235.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"518.94,-236.56 523.74,-244.18 524.74,-235.23 518.94,-236.56\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-110.92\" font-family=\"Times,serif\" font-size=\"14.00\"> A </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q8 -->\n",
       "<g id=\"edge37\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M359.62,-44.18C383.06,-42.7 423.73,-43.44 451.58,-62.12 508.79,-100.48 523.33,-187.34 526.95,-234.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"524,-235.12 527.53,-243.4 529.93,-234.72 524,-235.12\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-65.92\" font-family=\"Times,serif\" font-size=\"14.00\"> C </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q8 -->\n",
       "<g id=\"edge38\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M357.73,-37.51C380.19,-27.16 420.91,-12.97 451.58,-28.12 475.18,-39.77 476.6,-51.21 487.58,-75.12 511.81,-127.85 521.73,-195.41 525.65,-234.73\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"522.73,-235.43 526.48,-243.61 528.65,-234.87 522.73,-235.43\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-31.92\" font-family=\"Times,serif\" font-size=\"14.00\"> G </text>\n",
       "</g>\n",
       "<!-- q7&#45;&gt;q8 -->\n",
       "<g id=\"edge40\" class=\"edge\">\n",
       "<title>q7&#45;&gt;q8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M355.5,-33.79C369.16,-23.05 390.76,-8.4 412.59,-3.12 448.16,5.49 470.23,-4.9 487.58,-37.12 522.01,-101.03 528.09,-188.06 528.64,-234.6\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"525.66,-234.86 528.68,-243.35 531.61,-234.84 525.66,-234.86\"/>\n",
       "<text text-anchor=\"middle\" x=\"432.08\" y=\"-6.92\" font-family=\"Times,serif\" font-size=\"14.00\"> T </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x1217af6d8>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "big_nfa.show_diagram(\"CGC\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "suburban-consequence",
   "metadata": {},
   "source": [
    "```text\n",
    "          [Accepted]                         \n",
    "Step: Current state: Input symbol: New state:\n",
    "1                →q1             C         q4\n",
    "2                 q4             G         q5\n",
    "3                 q5             C        *q8\n",
    "```\n",
    "\n",
    "![alt text](https://github.com/lewiuberg/visual-automata/blob/master/images/big_nfa.png?raw=true \"big_nfa\")\n",
    "\n",
    "## Authors\n",
    "\n",
    "- **[Lewi Lie Uberg](https://github.com/lewiuberg)** - [uberg.me](https://uberg.me/)\n",
    "\n",
    "## License\n",
    "\n",
    "This project is licensed under the MIT License - see the [LICENSE.md](https://github.com/lewiuberg/visual-automata/blob/master/LICENSE.txt) file for details\n",
    "\n",
    "## Acknowledgments\n",
    "\n",
    "- [Caleb Evans](https://github.com/caleb531) for his work on automata-lib.\n",
    "- [Geir Arne Hjelle](https://github.com/gahjelle), [Michal Porteš](https://github.com/mportesdev), and [Bart Willems](https://github.com/bart-r-willems) for their general counsel.\n",
    "- [Dr. Seifedine Kadry](https://www.noroff.no/en/contact/staff/53-academic/423-seifedine-kadry). My _Further Discrete Mathematics_ professor at **Noroff University College**, for teaching me Automata.\n",
    "- [JFLAP](http://www.jflap.org) for their work on a GUI based Automata application."
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "encoding": "# -*- coding: utf-8 -*-",
   "formats": "ipynb,py:light,md"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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": 5
}