{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nondeterministic finite automata\n",
    "================================"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tock import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating NFAs\n",
    "\n",
    "NFAs are loaded and created similarly to DFAs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = read_csv(\"examples/sipser-1-27.csv\")\n",
    "m.is_finite(), m.is_deterministic()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style=\"font-family: Courier, monospace;\">\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\"></th>\n",
       "    <th style=\"text-align: left\">ε</th>\n",
       "    <th style=\"text-align: left\">0</th>\n",
       "    <th style=\"text-align: left\">1</th>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">&gt;q1</th>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q1</td>\n",
       "    <td style=\"text-align: left\">{q1,q2}</td>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">q2</th>\n",
       "    <td style=\"text-align: left\">q3</td>\n",
       "    <td style=\"text-align: left\">q3</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">q3</th>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q4</td>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">@q4</th>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q4</td>\n",
       "    <td style=\"text-align: left\">q4</td>\n",
       "  </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "<tock.tables.Table at 0x10c609fa0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_table(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are two main differences in this table from a DFA. First, a cell can have more than one state. For example, if the machine is in state `q1` and the next input symbol is a `1`, then the machine can change to either `q1` or `q2`. Use curly braces for sets of states. (It's an error to omit them.) If a cell has no states, either write `{}` or `∅` or leave the cell blank.\n",
    "\n",
    "The second difference is that there is a column for the empty string, which can be written either as `ε` or `&`. (The ampersand is supposed to look like \"et\", so I figured it would be a good approximation to ε, which is a Greek \"e\".) If the machine is in state `q2`, then it can change to state `q3` _without_ reading in any input symbols.\n",
    "\n",
    "This is what the state transition diagram looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"292pt\" height=\"81pt\" viewBox=\"0.00 0.00 292.00 81.00\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 77)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-77 288,-77 288,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.83,-21C57.83,-21 48.17,-21 48.17,-21 45.33,-21 42.5,-18.17 42.5,-15.33 42.5,-15.33 42.5,-9.67 42.5,-9.67 42.5,-6.83 45.33,-4 48.17,-4 48.17,-4 57.83,-4 57.83,-4 60.67,-4 63.5,-6.83 63.5,-9.67 63.5,-9.67 63.5,-15.33 63.5,-15.33 63.5,-18.17 60.67,-21 57.83,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"46.5\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.15,-12.5C3.02,-12.5 22.58,-12.5 36.88,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"42.24,-12.5 37.24,-14.75 39.74,-12.5 37.24,-12.5 37.24,-12.5 37.24,-12.5 39.74,-12.5 37.24,-10.25 42.24,-12.5 42.24,-12.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M200.33,-21C200.33,-21 190.67,-21 190.67,-21 187.83,-21 185,-18.17 185,-15.33 185,-15.33 185,-9.67 185,-9.67 185,-6.83 187.83,-4 190.67,-4 190.67,-4 200.33,-4 200.33,-4 203.17,-4 206,-6.83 206,-9.67 206,-9.67 206,-15.33 206,-15.33 206,-18.17 203.17,-21 200.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"189\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.83,-21C273.83,-21 264.17,-21 264.17,-21 261.33,-21 258.5,-18.17 258.5,-15.33 258.5,-15.33 258.5,-9.67 258.5,-9.67 258.5,-6.83 261.33,-4 264.17,-4 264.17,-4 273.83,-4 273.83,-4 276.67,-4 279.5,-6.83 279.5,-9.67 279.5,-9.67 279.5,-15.33 279.5,-15.33 279.5,-18.17 276.67,-21 273.83,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M275.17,-25C275.17,-25 262.83,-25 262.83,-25 258.67,-25 254.5,-20.83 254.5,-16.67 254.5,-16.67 254.5,-8.33 254.5,-8.33 254.5,-4.17 258.67,0 262.83,0 262.83,0 275.17,0 275.17,0 279.33,0 283.5,-4.17 283.5,-8.33 283.5,-8.33 283.5,-16.67 283.5,-16.67 283.5,-20.83 279.33,-25 275.17,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"262.5\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>0-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M206.14,-12.5C217.11,-12.5 235.29,-12.5 249.11,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"254.36,-12.5 249.36,-14.75 251.86,-12.5 249.36,-12.5 249.36,-12.5 249.36,-12.5 251.86,-12.5 249.36,-10.25 254.36,-12.5 254.36,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"227\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M131.33,-21C131.33,-21 121.67,-21 121.67,-21 118.83,-21 116,-18.17 116,-15.33 116,-15.33 116,-9.67 116,-9.67 116,-6.83 118.83,-4 121.67,-4 121.67,-4 131.33,-4 131.33,-4 134.17,-4 137,-6.83 137,-9.67 137,-9.67 137,-15.33 137,-15.33 137,-18.17 134.17,-21 131.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"120\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M137.1,-12.5C148.24,-12.5 166.75,-12.5 179.73,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"184.92,-12.5 179.92,-14.75 182.42,-12.5 179.92,-12.5 179.92,-12.5 179.92,-12.5 182.42,-12.5 179.92,-10.25 184.92,-12.5 184.92,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"158\" y=\"-32.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "<text text-anchor=\"start\" x=\"158\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M63.64,-12.5C75.62,-12.5 96.2,-12.5 110.31,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"115.55,-12.5 110.55,-14.75 113.05,-12.5 110.55,-12.5 110.55,-12.5 110.55,-12.5 113.05,-12.5 110.55,-10.25 115.55,-12.5 115.55,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"89\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M48.23,-21.19C45.6,-29.67 47.19,-39 53,-39 57.63,-39 59.58,-33.08 58.85,-26.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.77,-21.19 60.99,-25.62 58.28,-23.63 58.79,-26.08 58.79,-26.08 58.79,-26.08 58.28,-23.63 56.59,-26.54 57.77,-21.19 57.77,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"50\" y=\"-58.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "<text text-anchor=\"start\" x=\"50\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M262.64,-25.03C260.57,-34.03 262.69,-43 269,-43 274.13,-43 276.49,-37.08 276.08,-30.03\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"275.36,-25.03 278.3,-29.66 275.72,-27.51 276.07,-29.98 276.07,-29.98 276.07,-29.98 275.72,-27.51 273.85,-30.3 275.36,-25.03 275.36,-25.03\"/>\n",
       "<text text-anchor=\"start\" x=\"266\" y=\"-62.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "<text text-anchor=\"start\" x=\"266\" y=\"-48.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "to_graph(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it's a little easier to see that this machine accepts strings that contain either `101` or `11`. \n",
    "\n",
    "## Running NFAs\n",
    "\n",
    "Let's run the automaton on a string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"607pt\" height=\"217pt\" viewBox=\"0.00 0.00 607.00 216.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 212.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-212.5 603,-212.5 603,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.33,-93C62.33,-93 52.67,-93 52.67,-93 49.83,-93 47,-90.17 47,-87.33 47,-87.33 47,-81.67 47,-81.67 47,-78.83 49.83,-76 52.67,-76 52.67,-76 62.33,-76 62.33,-76 65.17,-76 68,-78.83 68,-81.67 68,-81.67 68,-87.33 68,-87.33 68,-90.17 65.17,-93 62.33,-93\"/>\n",
       "<text text-anchor=\"start\" x=\"51\" y=\"-82\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.16,-84.5C3.27,-84.5 25.82,-84.5 41.47,-84.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"46.88,-84.5 41.88,-86.75 44.38,-84.5 41.88,-84.5 41.88,-84.5 41.88,-84.5 44.38,-84.5 41.88,-82.25 46.88,-84.5 46.88,-84.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.33,-70C149.33,-70 139.67,-70 139.67,-70 136.83,-70 134,-67.17 134,-64.33 134,-64.33 134,-58.67 134,-58.67 134,-55.83 136.83,-53 139.67,-53 139.67,-53 149.33,-53 149.33,-53 152.17,-53 155,-55.83 155,-58.67 155,-58.67 155,-64.33 155,-64.33 155,-67.17 152.17,-70 149.33,-70\"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-59\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.33,-17C149.33,-17 139.67,-17 139.67,-17 136.83,-17 134,-14.17 134,-11.33 134,-11.33 134,-5.67 134,-5.67 134,-2.83 136.83,0 139.67,0 139.67,0 149.33,0 149.33,0 152.17,0 155,-2.83 155,-5.67 155,-5.67 155,-11.33 155,-11.33 155,-14.17 152.17,-17 149.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>0-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M144.5,-52.85C144.5,-42.63 144.5,-32.42 144.5,-22.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"144.5,-17.2 146.75,-22.2 144.5,-19.7 144.5,-22.2 144.5,-22.2 144.5,-22.2 144.5,-19.7 142.25,-22.2 144.5,-17.2 144.5,-17.2\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-58C236.33,-58 226.67,-58 226.67,-58 223.83,-58 221,-55.17 221,-52.33 221,-52.33 221,-46.67 221,-46.67 221,-43.83 223.83,-41 226.67,-41 226.67,-41 236.33,-41 236.33,-41 239.17,-41 242,-43.83 242,-46.67 242,-46.67 242,-52.33 242,-52.33 242,-55.17 239.17,-58 236.33,-58\"/>\n",
       "<text text-anchor=\"start\" x=\"225\" y=\"-47\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>0-&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M155.25,-60.12C170.11,-58.03 198.52,-54.01 215.86,-51.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.86,-50.86 216.23,-53.79 218.39,-51.21 215.91,-51.56 215.91,-51.56 215.91,-51.56 218.39,-51.21 215.6,-49.33 220.86,-50.86 220.86,-50.86\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.33,-110C149.33,-110 139.67,-110 139.67,-110 136.83,-110 134,-107.17 134,-104.33 134,-104.33 134,-98.67 134,-98.67 134,-95.83 136.83,-93 139.67,-93 139.67,-93 149.33,-93 149.33,-93 152.17,-93 155,-95.83 155,-98.67 155,-98.67 155,-104.33 155,-104.33 155,-107.17 152.17,-110 149.33,-110\"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-99\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-115C236.33,-115 226.67,-115 226.67,-115 223.83,-115 221,-112.17 221,-109.33 221,-109.33 221,-103.67 221,-103.67 221,-100.83 223.83,-98 226.67,-98 226.67,-98 236.33,-98 236.33,-98 239.17,-98 242,-100.83 242,-103.67 242,-103.67 242,-109.33 242,-109.33 242,-112.17 239.17,-115 236.33,-115\"/>\n",
       "<text text-anchor=\"start\" x=\"225\" y=\"-104\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M155.25,-102.07C170.11,-102.95 198.52,-104.62 215.86,-105.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.86,-105.93 215.74,-107.89 218.37,-105.79 215.87,-105.64 215.87,-105.64 215.87,-105.64 218.37,-105.79 216,-103.39 220.86,-105.93 220.86,-105.93\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.25,-81.86C83.11,-77.84 111.52,-70.15 128.86,-65.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"133.86,-64.11 129.62,-67.59 131.45,-64.76 129.04,-65.41 129.04,-65.41 129.04,-65.41 131.45,-64.76 128.45,-63.24 133.86,-64.11 133.86,-64.11\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.25,-86.45C83.11,-89.42 111.52,-95.1 128.86,-98.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"133.86,-99.57 128.52,-100.8 131.41,-99.08 128.96,-98.59 128.96,-98.59 128.96,-98.59 131.41,-99.08 129.4,-96.39 133.86,-99.57 133.86,-99.57\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-115C323.33,-115 313.67,-115 313.67,-115 310.83,-115 308,-112.17 308,-109.33 308,-109.33 308,-103.67 308,-103.67 308,-100.83 310.83,-98 313.67,-98 313.67,-98 323.33,-98 323.33,-98 326.17,-98 329,-100.83 329,-103.67 329,-103.67 329,-109.33 329,-109.33 329,-112.17 326.17,-115 323.33,-115\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-104\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M410.33,-152C410.33,-152 400.67,-152 400.67,-152 397.83,-152 395,-149.17 395,-146.33 395,-146.33 395,-140.67 395,-140.67 395,-137.83 397.83,-135 400.67,-135 400.67,-135 410.33,-135 410.33,-135 413.17,-135 416,-137.83 416,-140.67 416,-140.67 416,-146.33 416,-146.33 416,-149.17 413.17,-152 410.33,-152\"/>\n",
       "<text text-anchor=\"start\" x=\"399\" y=\"-141\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;9 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>3-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.25,-110.74C344.11,-117.21 372.52,-129.58 389.86,-137.13\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"394.86,-139.31 389.38,-139.37 392.57,-138.31 390.28,-137.31 390.28,-137.31 390.28,-137.31 392.57,-138.31 391.18,-135.25 394.86,-139.31 394.86,-139.31\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M410.33,-117C410.33,-117 400.67,-117 400.67,-117 397.83,-117 395,-114.17 395,-111.33 395,-111.33 395,-105.67 395,-105.67 395,-102.83 397.83,-100 400.67,-100 400.67,-100 410.33,-100 410.33,-100 413.17,-100 416,-102.83 416,-105.67 416,-105.67 416,-111.33 416,-111.33 416,-114.17 413.17,-117 410.33,-117\"/>\n",
       "<text text-anchor=\"start\" x=\"399\" y=\"-106\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;10 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>3-&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.25,-106.73C344.11,-107.08 372.52,-107.75 389.86,-108.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"394.86,-108.27 389.81,-110.4 392.36,-108.21 389.86,-108.16 389.86,-108.16 389.86,-108.16 392.36,-108.21 389.92,-105.91 394.86,-108.27 394.86,-108.27\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;3 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>5-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.25,-106.5C256.98,-106.5 285.03,-106.5 302.41,-106.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.86,-106.5 302.86,-108.75 305.36,-106.5 302.86,-106.5 302.86,-106.5 302.86,-106.5 305.36,-106.5 302.86,-104.25 307.86,-106.5 307.86,-106.5\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-150C323.33,-150 313.67,-150 313.67,-150 310.83,-150 308,-147.17 308,-144.33 308,-144.33 308,-138.67 308,-138.67 308,-135.83 310.83,-133 313.67,-133 313.67,-133 323.33,-133 323.33,-133 326.17,-133 329,-135.83 329,-138.67 329,-138.67 329,-144.33 329,-144.33 329,-147.17 326.17,-150 323.33,-150\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-139\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;7 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5-&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.25,-110.51C257.11,-116.63 285.52,-128.33 302.86,-135.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.86,-137.53 302.38,-137.71 305.55,-136.58 303.24,-135.63 303.24,-135.63 303.24,-135.63 305.55,-136.58 304.1,-133.55 307.86,-137.53 307.86,-137.53\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-39C323.33,-39 313.67,-39 313.67,-39 310.83,-39 308,-36.17 308,-33.33 308,-33.33 308,-27.67 308,-27.67 308,-24.83 310.83,-22 313.67,-22 313.67,-22 323.33,-22 323.33,-22 326.17,-22 329,-24.83 329,-27.67 329,-27.67 329,-33.33 329,-33.33 329,-36.17 326.17,-39 323.33,-39\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-28\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;8 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>6-&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.25,-47.32C257.11,-44 285.52,-37.65 302.86,-33.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.86,-32.65 303.47,-35.94 305.42,-33.2 302.98,-33.74 302.98,-33.74 302.98,-33.74 305.42,-33.2 302.49,-31.55 307.86,-32.65 307.86,-32.65\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-78C323.33,-78 313.67,-78 313.67,-78 310.83,-78 308,-75.17 308,-72.33 308,-72.33 308,-66.67 308,-66.67 308,-63.83 310.83,-61 313.67,-61 313.67,-61 323.33,-61 323.33,-61 326.17,-61 329,-63.83 329,-66.67 329,-66.67 329,-72.33 329,-72.33 329,-75.17 326.17,-78 323.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;18 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>7-&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M307.65,-138.2C297.18,-134.37 281.91,-126.93 275,-114.5 271.33,-107.9 271.38,-104.13 275,-97.5 280.91,-86.66 293.02,-79.39 302.97,-74.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.64,-73.04 303.88,-77.03 305.33,-74 303.02,-74.95 303.02,-74.95 303.02,-74.95 305.33,-74 302.16,-72.88 307.64,-73.04 307.64,-73.04\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M410.33,-29C410.33,-29 400.67,-29 400.67,-29 397.83,-29 395,-26.17 395,-23.33 395,-23.33 395,-17.67 395,-17.67 395,-14.83 397.83,-12 400.67,-12 400.67,-12 410.33,-12 410.33,-12 413.17,-12 416,-14.83 416,-17.67 416,-17.67 416,-23.33 416,-23.33 416,-26.17 413.17,-29 410.33,-29\"/>\n",
       "<text text-anchor=\"start\" x=\"399\" y=\"-18\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;19 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>8-&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.25,-29.35C344.11,-27.6 372.52,-24.26 389.86,-22.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"394.86,-21.63 390.16,-24.45 392.38,-21.93 389.9,-22.22 389.9,-22.22 389.9,-22.22 392.38,-21.93 389.63,-19.98 394.86,-21.63 394.86,-21.63\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-152C497.33,-152 487.67,-152 487.67,-152 484.83,-152 482,-149.17 482,-146.33 482,-146.33 482,-140.67 482,-140.67 482,-137.83 484.83,-135 487.67,-135 487.67,-135 497.33,-135 497.33,-135 500.17,-135 503,-137.83 503,-140.67 503,-140.67 503,-146.33 503,-146.33 503,-149.17 500.17,-152 497.33,-152\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-141\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;20 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>9-&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.25,-143.5C430.98,-143.5 459.03,-143.5 476.41,-143.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.86,-143.5 476.86,-145.75 479.36,-143.5 476.86,-143.5 476.86,-143.5 476.86,-143.5 479.36,-143.5 476.86,-141.25 481.86,-143.5 481.86,-143.5\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-101C497.33,-101 487.67,-101 487.67,-101 484.83,-101 482,-98.17 482,-95.33 482,-95.33 482,-89.67 482,-89.67 482,-86.83 484.83,-84 487.67,-84 487.67,-84 497.33,-84 497.33,-84 500.17,-84 503,-86.83 503,-89.67 503,-89.67 503,-95.33 503,-95.33 503,-98.17 500.17,-101 497.33,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-90\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;21 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>10-&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.25,-106.66C431.11,-103.87 459.52,-98.52 476.86,-95.26\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.86,-94.31 477.37,-97.45 479.41,-94.78 476.95,-95.24 476.95,-95.24 476.95,-95.24 479.41,-94.78 476.53,-93.03 481.86,-94.31 481.86,-94.31\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M410.33,-64C410.33,-64 400.67,-64 400.67,-64 397.83,-64 395,-61.17 395,-58.33 395,-58.33 395,-52.67 395,-52.67 395,-49.83 397.83,-47 400.67,-47 400.67,-47 410.33,-47 410.33,-47 413.17,-47 416,-49.83 416,-52.67 416,-52.67 416,-58.33 416,-58.33 416,-61.17 413.17,-64 410.33,-64\"/>\n",
       "<text text-anchor=\"start\" x=\"399\" y=\"-53\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;22 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>10-&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M405.5,-99.85C405.5,-89.63 405.5,-79.42 405.5,-69.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"405.5,-64.2 407.75,-69.2 405.5,-66.7 405.5,-69.2 405.5,-69.2 405.5,-69.2 405.5,-66.7 403.25,-69.2 405.5,-64.2 405.5,-64.2\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>11</title>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>12</title>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>11-&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M77.36,-192.5C89.89,-192.5 106.42,-192.5 119.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"124.98,-192.5 119.98,-194.75 122.48,-192.5 119.98,-192.5 119.98,-192.5 119.98,-192.5 122.48,-192.5 119.98,-190.25 124.98,-192.5 124.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"98\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>13</title>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>12-&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M164.36,-192.5C176.89,-192.5 193.42,-192.5 206.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"211.98,-192.5 206.98,-194.75 209.48,-192.5 206.98,-192.5 206.98,-192.5 206.98,-192.5 209.48,-192.5 206.98,-190.25 211.98,-192.5 211.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"185\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>14</title>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>13-&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M251.36,-192.5C263.89,-192.5 280.42,-192.5 293.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"298.98,-192.5 293.98,-194.75 296.48,-192.5 293.98,-192.5 293.98,-192.5 293.98,-192.5 296.48,-192.5 293.98,-190.25 298.98,-192.5 298.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"272\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>15</title>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>14-&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M338.36,-192.5C350.89,-192.5 367.42,-192.5 380.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"385.98,-192.5 380.98,-194.75 383.48,-192.5 380.98,-192.5 380.98,-192.5 380.98,-192.5 383.48,-192.5 380.98,-190.25 385.98,-192.5 385.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"359\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>16</title>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>15-&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M425.36,-192.5C437.89,-192.5 454.42,-192.5 467.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"472.98,-192.5 467.98,-194.75 470.48,-192.5 467.98,-192.5 467.98,-192.5 467.98,-192.5 470.48,-192.5 467.98,-190.25 472.98,-192.5 472.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"446\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>17</title>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>16-&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M512.36,-192.5C524.89,-192.5 541.42,-192.5 554.83,-192.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"559.98,-192.5 554.98,-194.75 557.48,-192.5 554.98,-192.5 554.98,-192.5 554.98,-192.5 557.48,-192.5 554.98,-190.25 559.98,-192.5 559.98,-192.5\"/>\n",
       "<text text-anchor=\"start\" x=\"533\" y=\"-198.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 18&#45;&gt;19 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>18-&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.25,-63.88C344.24,-55.24 373.01,-38.65 390.31,-28.68\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"394.86,-26.06 391.66,-30.5 392.7,-27.3 390.53,-28.55 390.53,-28.55 390.53,-28.55 392.7,-27.3 389.41,-26.6 394.86,-26.06 394.86,-26.06\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-37C497.33,-37 487.67,-37 487.67,-37 484.83,-37 482,-34.17 482,-31.33 482,-31.33 482,-25.67 482,-25.67 482,-22.83 484.83,-20 487.67,-20 487.67,-20 497.33,-20 497.33,-20 500.17,-20 503,-22.83 503,-25.67 503,-25.67 503,-31.33 503,-31.33 503,-34.17 500.17,-37 497.33,-37\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-26\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;23 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>19-&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.25,-21.42C431.11,-22.82 459.52,-25.49 476.86,-27.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.86,-27.59 476.67,-29.36 479.37,-27.36 476.89,-27.12 476.89,-27.12 476.89,-27.12 479.37,-27.36 477.1,-24.88 481.86,-27.59 481.86,-27.59\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node26\" class=\"node\">\n",
       "<title>24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-166C584.33,-166 574.67,-166 574.67,-166 571.83,-166 569,-163.17 569,-160.33 569,-160.33 569,-154.67 569,-154.67 569,-151.83 571.83,-149 574.67,-149 574.67,-149 584.33,-149 584.33,-149 587.17,-149 590,-151.83 590,-154.67 590,-154.67 590,-160.33 590,-160.33 590,-163.17 587.17,-166 584.33,-166\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-155\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 20&#45;&gt;24 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>20-&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-145.11C518.11,-147.55 546.52,-152.23 563.86,-155.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"568.86,-155.91 563.56,-157.32 566.4,-155.51 563.93,-155.1 563.93,-155.1 563.93,-155.1 566.4,-155.51 564.3,-152.88 568.86,-155.91 568.86,-155.91\"/>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node27\" class=\"node\">\n",
       "<title>25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-131C584.33,-131 574.67,-131 574.67,-131 571.83,-131 569,-128.17 569,-125.33 569,-125.33 569,-119.67 569,-119.67 569,-116.83 571.83,-114 574.67,-114 574.67,-114 584.33,-114 584.33,-114 587.17,-114 590,-116.83 590,-119.67 590,-119.67 590,-125.33 590,-125.33 590,-128.17 587.17,-131 584.33,-131\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-120\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 20&#45;&gt;25 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>20-&gt;25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-141.09C518.11,-137.42 546.52,-130.4 563.86,-126.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"568.86,-124.88 564.55,-128.26 566.44,-125.48 564.01,-126.08 564.01,-126.08 564.01,-126.08 566.44,-125.48 563.47,-123.9 568.86,-124.88 568.86,-124.88\"/>\n",
       "</g>\n",
       "<!-- 26 -->\n",
       "<g id=\"node28\" class=\"node\">\n",
       "<title>26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-39C584.33,-39 574.67,-39 574.67,-39 571.83,-39 569,-36.17 569,-33.33 569,-33.33 569,-27.67 569,-27.67 569,-24.83 571.83,-22 574.67,-22 574.67,-22 584.33,-22 584.33,-22 587.17,-22 590,-24.83 590,-27.67 590,-27.67 590,-33.33 590,-33.33 590,-36.17 587.17,-39 584.33,-39\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M585.67,-43C585.67,-43 573.33,-43 573.33,-43 569.17,-43 565,-38.83 565,-34.67 565,-34.67 565,-26.33 565,-26.33 565,-22.17 569.17,-18 573.33,-18 573.33,-18 585.67,-18 585.67,-18 589.83,-18 594,-22.17 594,-26.33 594,-26.33 594,-34.67 594,-34.67 594,-38.83 589.83,-43 585.67,-43\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-28\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 21&#45;&gt;26 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>21-&gt;26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-85.39C517.24,-75.18 543.24,-56.22 560.71,-43.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"564.96,-40.38 562.24,-45.14 562.94,-41.85 560.92,-43.33 560.92,-43.33 560.92,-43.33 562.94,-41.85 559.59,-41.51 564.96,-40.38 564.96,-40.38\"/>\n",
       "</g>\n",
       "<!-- 23&#45;&gt;26 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>23-&gt;26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-28.73C517,-29.05 542.36,-29.65 559.81,-30.06\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"564.96,-30.18 559.9,-32.31 562.46,-30.12 559.96,-30.06 559.96,-30.06 559.96,-30.06 562.46,-30.12 560.01,-27.81 564.96,-30.18 564.96,-30.18\"/>\n",
       "</g>\n",
       "<!-- 27 -->\n",
       "<g id=\"node29\" class=\"node\">\n",
       "<title>27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-78C584.33,-78 574.67,-78 574.67,-78 571.83,-78 569,-75.17 569,-72.33 569,-72.33 569,-66.67 569,-66.67 569,-63.83 571.83,-61 574.67,-61 574.67,-61 584.33,-61 584.33,-61 587.17,-61 590,-63.83 590,-66.67 590,-66.67 590,-72.33 590,-72.33 590,-75.17 587.17,-78 584.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 25&#45;&gt;27 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>25-&gt;27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M579.5,-113.85C579.5,-103.63 579.5,-93.42 579.5,-83.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"579.5,-78.2 581.75,-83.2 579.5,-80.7 579.5,-83.2 579.5,-83.2 579.5,-83.2 579.5,-80.7 577.25,-83.2 579.5,-78.2 579.5,-78.2\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, \"1 0 1 1 0 1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the run graph is more interesting than for the DFA. As before, each node indicates a configuration, that is, a state that the machine can be in at a particular time. Nodes in the same column correspond to the same input position. An edge between two configurations means that the automaton can move from one to the other. Note that unlike in a DFA run, a node can have more than one outgoing edge. Since there is a path that ends with a double node, the machine accepted the string.\n",
    "\n",
    "Previously, we used `only_path()` to display a sequence of configurations. That won't work here, because there are many paths. Instead, we can use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style=\"font-family: Courier, monospace;\">\n",
       "  <tr><td style=\"text-align: left\">q1</td><td style=\"text-align: left\">[1] 0 1 1 0 1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q1</td><td style=\"text-align: left\">[0] 1 1 0 1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q1</td><td style=\"text-align: left\">[1] 1 0 1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q1</td><td style=\"text-align: left\">[1] 0 1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q2</td><td style=\"text-align: left\">[0] 1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q3</td><td style=\"text-align: left\">1</td></tr>\n",
       "  <tr><td style=\"text-align: left\">q4</td><td style=\"text-align: left\">ε</td></tr>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<tock.machines.Path at 0x10c6e7160>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "run(m, '1 0 1 1 0 1').shortest_path()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's another string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"607pt\" height=\"172pt\" viewBox=\"0.00 0.00 607.00 171.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 167.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-167.5 603,-167.5 603,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.33,-70C62.33,-70 52.67,-70 52.67,-70 49.83,-70 47,-67.17 47,-64.33 47,-64.33 47,-58.67 47,-58.67 47,-55.83 49.83,-53 52.67,-53 52.67,-53 62.33,-53 62.33,-53 65.17,-53 68,-55.83 68,-58.67 68,-58.67 68,-64.33 68,-64.33 68,-67.17 65.17,-70 62.33,-70\"/>\n",
       "<text text-anchor=\"start\" x=\"51\" y=\"-59\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;18 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.16,-61.5C3.27,-61.5 25.82,-61.5 41.47,-61.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"46.88,-61.5 41.88,-63.75 44.38,-61.5 41.88,-61.5 41.88,-61.5 41.88,-61.5 44.38,-61.5 41.88,-59.25 46.88,-61.5 46.88,-61.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-68C236.33,-68 226.67,-68 226.67,-68 223.83,-68 221,-65.17 221,-62.33 221,-62.33 221,-56.67 221,-56.67 221,-53.83 223.83,-51 226.67,-51 226.67,-51 236.33,-51 236.33,-51 239.17,-51 242,-53.83 242,-56.67 242,-56.67 242,-62.33 242,-62.33 242,-65.17 239.17,-68 236.33,-68\"/>\n",
       "<text text-anchor=\"start\" x=\"225\" y=\"-57\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-105C584.33,-105 574.67,-105 574.67,-105 571.83,-105 569,-102.17 569,-99.33 569,-99.33 569,-93.67 569,-93.67 569,-90.83 571.83,-88 574.67,-88 574.67,-88 584.33,-88 584.33,-88 587.17,-88 590,-90.83 590,-93.67 590,-93.67 590,-99.33 590,-99.33 590,-102.17 587.17,-105 584.33,-105\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-94\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-105C497.33,-105 487.67,-105 487.67,-105 484.83,-105 482,-102.17 482,-99.33 482,-99.33 482,-93.67 482,-93.67 482,-90.83 484.83,-88 487.67,-88 487.67,-88 497.33,-88 497.33,-88 500.17,-88 503,-90.83 503,-93.67 503,-93.67 503,-99.33 503,-99.33 503,-102.17 500.17,-105 497.33,-105\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-94\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>2-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-96.5C517.98,-96.5 546.03,-96.5 563.41,-96.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"568.86,-96.5 563.86,-98.75 566.36,-96.5 563.86,-96.5 563.86,-96.5 563.86,-96.5 566.36,-96.5 563.86,-94.25 568.86,-96.5 568.86,-96.5\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-52C497.33,-52 487.67,-52 487.67,-52 484.83,-52 482,-49.17 482,-46.33 482,-46.33 482,-40.67 482,-40.67 482,-37.83 484.83,-35 487.67,-35 487.67,-35 497.33,-35 497.33,-35 500.17,-35 503,-37.83 503,-40.67 503,-40.67 503,-46.33 503,-46.33 503,-49.17 500.17,-52 497.33,-52\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-41\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;19 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>2-&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M492.5,-87.85C492.5,-77.63 492.5,-67.42 492.5,-57.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"492.5,-52.2 494.75,-57.2 492.5,-54.7 492.5,-57.2 492.5,-57.2 492.5,-57.2 492.5,-54.7 490.25,-57.2 492.5,-52.2 492.5,-52.2\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M584.33,-17C584.33,-17 574.67,-17 574.67,-17 571.83,-17 569,-14.17 569,-11.33 569,-11.33 569,-5.67 569,-5.67 569,-2.83 571.83,0 574.67,0 574.67,0 584.33,0 584.33,0 587.17,0 590,-2.83 590,-5.67 590,-5.67 590,-11.33 590,-11.33 590,-14.17 587.17,-17 584.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"573\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M497.33,-17C497.33,-17 487.67,-17 487.67,-17 484.83,-17 482,-14.17 482,-11.33 482,-11.33 482,-5.67 482,-5.67 482,-2.83 484.83,0 487.67,0 487.67,0 497.33,0 497.33,0 500.17,0 503,-2.83 503,-5.67 503,-5.67 503,-11.33 503,-11.33 503,-14.17 500.17,-17 497.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>4-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M503.25,-8.5C517.98,-8.5 546.03,-8.5 563.41,-8.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"568.86,-8.5 563.86,-10.75 566.36,-8.5 563.86,-8.5 563.86,-8.5 563.86,-8.5 566.36,-8.5 563.86,-6.25 568.86,-8.5 568.86,-8.5\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M410.33,-33C410.33,-33 400.67,-33 400.67,-33 397.83,-33 395,-30.17 395,-27.33 395,-27.33 395,-21.67 395,-21.67 395,-18.83 397.83,-16 400.67,-16 400.67,-16 410.33,-16 410.33,-16 413.17,-16 416,-18.83 416,-21.67 416,-21.67 416,-27.33 416,-27.33 416,-30.17 413.17,-33 410.33,-33\"/>\n",
       "<text text-anchor=\"start\" x=\"399\" y=\"-22\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;2 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>5-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.25,-32.76C431.37,-45.56 460.5,-70.24 477.75,-84.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.86,-88.34 476.59,-86.82 479.96,-86.72 478.05,-85.11 478.05,-85.11 478.05,-85.11 479.96,-86.72 479.5,-83.39 481.86,-88.34 481.86,-88.34\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>5-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.25,-22.66C431.11,-19.87 459.52,-14.52 476.86,-11.26\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.86,-10.31 477.37,-13.45 479.41,-10.78 476.95,-11.24 476.95,-11.24 476.95,-11.24 479.41,-10.78 476.53,-9.03 481.86,-10.31 481.86,-10.31\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>10</title>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;10 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>6-&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M164.36,-147.5C176.89,-147.5 193.42,-147.5 206.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"211.98,-147.5 206.98,-149.75 209.48,-147.5 206.98,-147.5 206.98,-147.5 206.98,-147.5 209.48,-147.5 206.98,-145.25 211.98,-147.5 211.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"185\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>7</title>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;6 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>7-&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M77.36,-147.5C89.89,-147.5 106.42,-147.5 119.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"124.98,-147.5 119.98,-149.75 122.48,-147.5 119.98,-147.5 119.98,-147.5 119.98,-147.5 122.48,-147.5 119.98,-145.25 124.98,-147.5 124.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"98\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>8</title>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>11</title>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;11 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>8-&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M425.36,-147.5C437.89,-147.5 454.42,-147.5 467.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"472.98,-147.5 467.98,-149.75 470.48,-147.5 467.98,-147.5 467.98,-147.5 467.98,-147.5 470.48,-147.5 467.98,-145.25 472.98,-147.5 472.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"446\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>9</title>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;8 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>9-&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M338.36,-147.5C350.89,-147.5 367.42,-147.5 380.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"385.98,-147.5 380.98,-149.75 383.48,-147.5 380.98,-147.5 380.98,-147.5 380.98,-147.5 383.48,-147.5 380.98,-145.25 385.98,-147.5 385.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"359\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;9 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>10-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M251.36,-147.5C263.89,-147.5 280.42,-147.5 293.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"298.98,-147.5 293.98,-149.75 296.48,-147.5 293.98,-147.5 293.98,-147.5 293.98,-147.5 296.48,-147.5 293.98,-145.25 298.98,-147.5 298.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"272\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>12</title>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>11-&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M512.36,-147.5C524.89,-147.5 541.42,-147.5 554.83,-147.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"559.98,-147.5 554.98,-149.75 557.48,-147.5 554.98,-147.5 554.98,-147.5 554.98,-147.5 557.48,-147.5 554.98,-145.25 559.98,-147.5 559.98,-147.5\"/>\n",
       "<text text-anchor=\"start\" x=\"533\" y=\"-153.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-33C323.33,-33 313.67,-33 313.67,-33 310.83,-33 308,-30.17 308,-27.33 308,-27.33 308,-21.67 308,-21.67 308,-18.83 310.83,-16 313.67,-16 313.67,-16 323.33,-16 323.33,-16 326.17,-16 329,-18.83 329,-21.67 329,-21.67 329,-27.33 329,-27.33 329,-30.17 326.17,-33 323.33,-33\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-22\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;5 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>13-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M329.25,-24.5C343.98,-24.5 372.03,-24.5 389.41,-24.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"394.86,-24.5 389.86,-26.75 392.36,-24.5 389.86,-24.5 389.86,-24.5 389.86,-24.5 392.36,-24.5 389.86,-22.25 394.86,-24.5 394.86,-24.5\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.33,-70C149.33,-70 139.67,-70 139.67,-70 136.83,-70 134,-67.17 134,-64.33 134,-64.33 134,-58.67 134,-58.67 134,-55.83 136.83,-53 139.67,-53 139.67,-53 149.33,-53 149.33,-53 152.17,-53 155,-55.83 155,-58.67 155,-58.67 155,-64.33 155,-64.33 155,-67.17 152.17,-70 149.33,-70\"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-59\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-121C236.33,-121 226.67,-121 226.67,-121 223.83,-121 221,-118.17 221,-115.33 221,-115.33 221,-109.67 221,-109.67 221,-106.83 223.83,-104 226.67,-104 226.67,-104 236.33,-104 236.33,-104 239.17,-104 242,-106.83 242,-109.67 242,-109.67 242,-115.33 242,-115.33 242,-118.17 239.17,-121 236.33,-121\"/>\n",
       "<text text-anchor=\"start\" x=\"225\" y=\"-110\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;16 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>14-&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M155.25,-67.35C170.24,-76.34 199.01,-93.61 216.31,-103.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.86,-106.72 215.42,-106.07 218.72,-105.43 216.58,-104.15 216.58,-104.15 216.58,-104.15 218.72,-105.43 217.73,-102.22 220.86,-106.72 220.86,-106.72\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-33C236.33,-33 226.67,-33 226.67,-33 223.83,-33 221,-30.17 221,-27.33 221,-27.33 221,-21.67 221,-21.67 221,-18.83 223.83,-16 226.67,-16 226.67,-16 236.33,-16 236.33,-16 239.17,-16 242,-18.83 242,-21.67 242,-21.67 242,-27.33 242,-27.33 242,-30.17 239.17,-33 236.33,-33\"/>\n",
       "<text text-anchor=\"start\" x=\"225\" y=\"-22\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;17 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>14-&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M155.25,-57.26C170.11,-50.79 198.52,-38.42 215.86,-30.87\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"220.86,-28.69 217.18,-32.75 218.57,-29.69 216.28,-30.69 216.28,-30.69 216.28,-30.69 218.57,-29.69 215.38,-28.63 220.86,-28.69 220.86,-28.69\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M323.33,-121C323.33,-121 313.67,-121 313.67,-121 310.83,-121 308,-118.17 308,-115.33 308,-115.33 308,-109.67 308,-109.67 308,-106.83 310.83,-104 313.67,-104 313.67,-104 323.33,-104 323.33,-104 326.17,-104 329,-106.83 329,-109.67 329,-109.67 329,-115.33 329,-115.33 329,-118.17 326.17,-121 323.33,-121\"/>\n",
       "<text text-anchor=\"start\" x=\"312\" y=\"-110\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>16-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M231.5,-103.85C231.5,-93.63 231.5,-83.42 231.5,-73.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"231.5,-68.2 233.75,-73.2 231.5,-70.7 231.5,-73.2 231.5,-73.2 231.5,-73.2 231.5,-70.7 229.25,-73.2 231.5,-68.2 231.5,-68.2\"/>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;15 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>16-&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.25,-112.5C256.98,-112.5 285.03,-112.5 302.41,-112.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.86,-112.5 302.86,-114.75 305.36,-112.5 302.86,-112.5 302.86,-112.5 302.86,-112.5 305.36,-112.5 302.86,-110.25 307.86,-112.5 307.86,-112.5\"/>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;13 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>17-&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.25,-24.5C256.98,-24.5 285.03,-24.5 302.41,-24.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"307.86,-24.5 302.86,-26.75 305.36,-24.5 302.86,-24.5 302.86,-24.5 302.86,-24.5 305.36,-24.5 302.86,-22.25 307.86,-24.5 307.86,-24.5\"/>\n",
       "</g>\n",
       "<!-- 18&#45;&gt;14 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>18-&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.25,-61.5C82.98,-61.5 111.03,-61.5 128.41,-61.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"133.86,-61.5 128.86,-63.75 131.36,-61.5 128.86,-61.5 128.86,-61.5 128.86,-61.5 131.36,-61.5 128.86,-59.25 133.86,-61.5 133.86,-61.5\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, \"0 1 0 0 1 0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The absence of a double node means that the string was rejected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a nondeterministic automaton, it's possible that there are infinitely many runs for a given input string. That's not a problem -- consider the following NFA, which (for some reason) loops through a bunch of epsilon transitions before reading in a single `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"144pt\" height=\"102pt\" viewBox=\"0.00 0.00 144.00 102.00\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 98)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-98 140,-98 140,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.33,-40C53.33,-40 43.67,-40 43.67,-40 40.83,-40 38,-37.17 38,-34.33 38,-34.33 38,-28.67 38,-28.67 38,-25.83 40.83,-23 43.67,-23 43.67,-23 53.33,-23 53.33,-23 56.17,-23 59,-25.83 59,-28.67 59,-28.67 59,-34.33 59,-34.33 59,-37.17 56.17,-40 53.33,-40\"/>\n",
       "<text text-anchor=\"start\" x=\"42\" y=\"-29\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.13,-31.5C2.79,-31.5 19.6,-31.5 32.5,-31.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"37.74,-31.5 32.74,-33.75 35.24,-31.5 32.74,-31.5 32.74,-31.5 32.74,-31.5 35.24,-31.5 32.74,-29.25 37.74,-31.5 37.74,-31.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.33,-60C126.33,-60 116.67,-60 116.67,-60 113.83,-60 111,-57.17 111,-54.33 111,-54.33 111,-48.67 111,-48.67 111,-45.83 113.83,-43 116.67,-43 116.67,-43 126.33,-43 126.33,-43 129.17,-43 132,-45.83 132,-48.67 132,-48.67 132,-54.33 132,-54.33 132,-57.17 129.17,-60 126.33,-60\"/>\n",
       "<text text-anchor=\"start\" x=\"115\" y=\"-49\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M115.84,-60.19C112.71,-68.67 114.6,-78 121.5,-78 127,-78 129.32,-72.08 128.45,-65.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"127.16,-60.19 130.55,-64.5 127.76,-62.61 128.36,-65.04 128.36,-65.04 128.36,-65.04 127.76,-62.61 126.18,-65.58 127.16,-60.19 127.16,-60.19\"/>\n",
       "<text text-anchor=\"start\" x=\"118.5\" y=\"-83.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59.08,-34.2C71.08,-37.58 91.77,-43.41 105.79,-47.36\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.62,-48.72 105.2,-49.53 108.21,-48.04 105.81,-47.36 105.81,-47.36 105.81,-47.36 108.21,-48.04 106.42,-45.2 110.62,-48.72 110.62,-48.72\"/>\n",
       "<text text-anchor=\"start\" x=\"80\" y=\"-47.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.33,-21C126.33,-21 116.67,-21 116.67,-21 113.83,-21 111,-18.17 111,-15.33 111,-15.33 111,-9.67 111,-9.67 111,-6.83 113.83,-4 116.67,-4 116.67,-4 126.33,-4 126.33,-4 129.17,-4 132,-6.83 132,-9.67 132,-9.67 132,-15.33 132,-15.33 132,-18.17 129.17,-21 126.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.67,-25C127.67,-25 115.33,-25 115.33,-25 111.17,-25 107,-20.83 107,-16.67 107,-16.67 107,-8.33 107,-8.33 107,-4.17 111.17,0 115.33,0 115.33,0 127.67,0 127.67,0 131.83,0 136,-4.17 136,-8.33 136,-8.33 136,-16.67 136,-16.67 136,-20.83 131.83,-25 127.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"115\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59,-23.38C64.01,-19.61 70.46,-15.53 77,-13.5 84.85,-11.06 93.9,-10.51 101.69,-10.69\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"106.86,-10.92 101.77,-12.95 104.37,-10.81 101.87,-10.7 101.87,-10.7 101.87,-10.7 104.37,-10.81 101.97,-8.45 106.86,-10.92 106.86,-10.92\"/>\n",
       "<text text-anchor=\"start\" x=\"80\" y=\"-19.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "m = read_csv(\"examples/nfaloop.csv\")\n",
    "to_graph(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"172pt\" height=\"143pt\" viewBox=\"0.00 0.00 172.00 142.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 138.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-138.5 168,-138.5 168,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.33,-88C62.33,-88 52.67,-88 52.67,-88 49.83,-88 47,-85.17 47,-82.33 47,-82.33 47,-76.67 47,-76.67 47,-73.83 49.83,-71 52.67,-71 52.67,-71 62.33,-71 62.33,-71 65.17,-71 68,-73.83 68,-76.67 68,-76.67 68,-82.33 68,-82.33 68,-85.17 65.17,-88 62.33,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"51\" y=\"-77\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.16,-79.5C3.27,-79.5 25.82,-79.5 41.47,-79.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"46.88,-79.5 41.88,-81.75 44.38,-79.5 41.88,-79.5 41.88,-79.5 41.88,-79.5 44.38,-79.5 41.88,-77.25 46.88,-79.5 46.88,-79.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M62.33,-17C62.33,-17 52.67,-17 52.67,-17 49.83,-17 47,-14.17 47,-11.33 47,-11.33 47,-5.67 47,-5.67 47,-2.83 49.83,0 52.67,0 52.67,0 62.33,0 62.33,0 65.17,0 68,-2.83 68,-5.67 68,-5.67 68,-11.33 68,-11.33 68,-14.17 65.17,-17 62.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"51\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M51.84,-17.19C48.71,-25.67 50.6,-35 57.5,-35 63,-35 65.32,-29.08 64.45,-22.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"63.16,-17.19 66.55,-21.5 63.76,-19.61 64.36,-22.04 64.36,-22.04 64.36,-22.04 63.76,-19.61 62.18,-22.58 63.16,-17.19 63.16,-17.19\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M149.33,-88C149.33,-88 139.67,-88 139.67,-88 136.83,-88 134,-85.17 134,-82.33 134,-82.33 134,-76.67 134,-76.67 134,-73.83 136.83,-71 139.67,-71 139.67,-71 149.33,-71 149.33,-71 152.17,-71 155,-73.83 155,-76.67 155,-76.67 155,-82.33 155,-82.33 155,-85.17 152.17,-88 149.33,-88\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M150.67,-92C150.67,-92 138.33,-92 138.33,-92 134.17,-92 130,-87.83 130,-83.67 130,-83.67 130,-75.33 130,-75.33 130,-71.17 134.17,-67 138.33,-67 138.33,-67 150.67,-67 150.67,-67 154.83,-67 159,-71.17 159,-75.33 159,-75.33 159,-83.67 159,-83.67 159,-87.83 154.83,-92 150.67,-92\"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-77\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.5,-70.72C57.5,-54.52 57.5,-38.33 57.5,-22.13\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.5,-17.1 59.75,-22.1 57.5,-19.6 57.5,-22.1 57.5,-22.1 57.5,-22.1 57.5,-19.6 55.25,-22.1 57.5,-17.1 57.5,-17.1\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.25,-79.5C82,-79.5 107.36,-79.5 124.81,-79.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"129.96,-79.5 124.96,-81.75 127.46,-79.5 124.96,-79.5 124.96,-79.5 124.96,-79.5 127.46,-79.5 124.96,-77.25 129.96,-79.5 129.96,-79.5\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M77.36,-118.5C89.89,-118.5 106.42,-118.5 119.83,-118.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"124.98,-118.5 119.98,-120.75 122.48,-118.5 119.98,-118.5 119.98,-118.5 119.98,-118.5 122.48,-118.5 119.98,-116.25 124.98,-118.5 124.98,-118.5\"/>\n",
       "<text text-anchor=\"start\" x=\"98\" y=\"-124.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, \"0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This graph represents an infinite number of runs, each of which loops in state `q1` for some number of times, then moves on to state `q2`."
   ]
  }
 ],
 "metadata": {
  "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.8.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
