{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pushdown automata"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tock import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating PDAs\n",
    "\n",
    "A pushdown automaton (PDA) can be created with `PushdownAutomaton()` or by reading from a file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True, True)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = read_csv(\"examples/sipser-2-14.csv\")\n",
    "m.is_finite(), m.is_pushdown(), 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\"></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\"></th>\n",
       "    <th style=\"text-align: left\">ε</th>\n",
       "    <th style=\"text-align: left\">$</th>\n",
       "    <th style=\"text-align: left\">ε</th>\n",
       "    <th style=\"text-align: left\">0</th>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">&gt;q1</th>\n",
       "    <td style=\"text-align: left\">q2,$</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\">q2</th>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q2,0</td>\n",
       "    <td style=\"text-align: left\">q3,ε</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\">q4,ε</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q3,ε</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\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "  </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "<tock.tables.Table at 0x106d83430>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_table(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first column lists the states, just as in a FA. The first row lists input symbols and the second row lists popped stack symbols.\n",
    "\n",
    "The cells contain pairs of new states and pushed stack symbols. So, if the machine is in state `q2`, and the next input symbol is `0`, then the machine stays in state `q2` and pushes a `0` onto the stack. If a cell has multiple tuples, then each tuple must be enclosed in parentheses (and curly braces are optional).\n",
    "\n",
    "Here's the state transition diagram:"
   ]
  },
  {
   "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=\"375pt\" height=\"63pt\" viewBox=\"0.00 0.00 375.00 63.00\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 59)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-59 371,-59 371,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.33,-21C53.33,-21 43.67,-21 43.67,-21 40.83,-21 38,-18.17 38,-15.33 38,-15.33 38,-9.67 38,-9.67 38,-6.83 40.83,-4 43.67,-4 43.67,-4 53.33,-4 53.33,-4 56.17,-4 59,-6.83 59,-9.67 59,-9.67 59,-15.33 59,-15.33 59,-18.17 56.17,-21 53.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"42\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.13,-12.5C2.79,-12.5 19.6,-12.5 32.5,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"37.74,-12.5 32.74,-14.75 35.24,-12.5 32.74,-12.5 32.74,-12.5 32.74,-12.5 35.24,-12.5 32.74,-10.25 37.74,-12.5 37.74,-12.5\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M153.33,-21C153.33,-21 143.67,-21 143.67,-21 140.83,-21 138,-18.17 138,-15.33 138,-15.33 138,-9.67 138,-9.67 138,-6.83 140.83,-4 143.67,-4 143.67,-4 153.33,-4 153.33,-4 156.17,-4 159,-6.83 159,-9.67 159,-9.67 159,-15.33 159,-15.33 159,-18.17 156.17,-21 153.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"142\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59.25,-12.5C76.5,-12.5 112.46,-12.5 132.75,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"137.78,-12.5 132.78,-14.75 135.28,-12.5 132.78,-12.5 132.78,-12.5 132.78,-12.5 135.28,-12.5 132.78,-10.25 137.78,-12.5 137.78,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"80.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,ε → $</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M357.33,-21C357.33,-21 347.67,-21 347.67,-21 344.83,-21 342,-18.17 342,-15.33 342,-15.33 342,-9.67 342,-9.67 342,-6.83 344.83,-4 347.67,-4 347.67,-4 357.33,-4 357.33,-4 360.17,-4 363,-6.83 363,-9.67 363,-9.67 363,-15.33 363,-15.33 363,-18.17 360.17,-21 357.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.67,-25C358.67,-25 346.33,-25 346.33,-25 342.17,-25 338,-20.83 338,-16.67 338,-16.67 338,-8.33 338,-8.33 338,-4.17 342.17,0 346.33,0 346.33,0 358.67,0 358.67,0 362.83,0 367,-4.17 367,-8.33 367,-8.33 367,-16.67 367,-16.67 367,-20.83 362.83,-25 358.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"346\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.05,-21.19C136.93,-29.67 139.42,-39 148.5,-39 155.88,-39 158.9,-32.84 157.57,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"155.95,-21.19 159.68,-25.2 156.75,-23.55 157.55,-25.92 157.55,-25.92 157.55,-25.92 156.75,-23.55 155.42,-26.64 155.95,-21.19 155.95,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"130.5\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">0,ε → 0</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M253.33,-21C253.33,-21 243.67,-21 243.67,-21 240.83,-21 238,-18.17 238,-15.33 238,-15.33 238,-9.67 238,-9.67 238,-6.83 240.83,-4 243.67,-4 243.67,-4 253.33,-4 253.33,-4 256.17,-4 259,-6.83 259,-9.67 259,-9.67 259,-15.33 259,-15.33 259,-18.17 256.17,-21 253.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"242\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.25,-12.5C176.5,-12.5 212.46,-12.5 232.75,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"237.78,-12.5 232.78,-14.75 235.28,-12.5 232.78,-12.5 232.78,-12.5 232.78,-12.5 235.28,-12.5 232.78,-10.25 237.78,-12.5 237.78,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"180.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1,0 → ε</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M259.28,-12.5C276.1,-12.5 310.8,-12.5 332.51,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"337.73,-12.5 332.73,-14.75 335.23,-12.5 332.73,-12.5 332.73,-12.5 332.73,-12.5 335.23,-12.5 332.73,-10.25 337.73,-12.5 337.73,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"280.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,$ → ε</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M241.05,-21.19C236.93,-29.67 239.42,-39 248.5,-39 255.88,-39 258.9,-32.84 257.57,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"255.95,-21.19 259.68,-25.2 256.75,-23.55 257.55,-25.92 257.55,-25.92 257.55,-25.92 256.75,-23.55 255.42,-26.64 255.95,-21.19 255.95,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"230.5\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">1,0 → ε</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 easier to see that it accepts strings of the form $\\texttt{0}^n\\texttt{1}^n$. If you draw the graph in a graph editor, use `->` for a right arrow.\n",
    "\n",
    "## Running PDAs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"747pt\" height=\"182pt\" viewBox=\"0.00 0.00 747.00 181.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 177.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-177.5 743,-177.5 743,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-131C68.33,-131 46.67,-131 46.67,-131 43.83,-131 41,-128.17 41,-125.33 41,-125.33 41,-119.67 41,-119.67 41,-116.83 43.83,-114 46.67,-114 46.67,-114 68.33,-114 68.33,-114 71.17,-114 74,-116.83 74,-119.67 74,-119.67 74,-125.33 74,-125.33 74,-128.17 71.17,-131 68.33,-131\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-120\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1,ε</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.16,-122.5C3.01,-122.5 20.55,-122.5 35.4,-122.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"40.72,-122.5 35.72,-124.75 38.22,-122.5 35.72,-122.5 35.72,-122.5 35.72,-122.5 38.22,-122.5 35.72,-120.25 40.72,-122.5 40.72,-122.5\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-78C68.33,-78 46.67,-78 46.67,-78 43.83,-78 41,-75.17 41,-72.33 41,-72.33 41,-66.67 41,-66.67 41,-63.83 43.83,-61 46.67,-61 46.67,-61 68.33,-61 68.33,-61 71.17,-61 74,-63.83 74,-66.67 74,-66.67 74,-72.33 74,-72.33 74,-75.17 71.17,-78 68.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,$</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>0-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.5,-113.85C57.5,-103.63 57.5,-93.42 57.5,-83.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.5,-78.2 59.75,-83.2 57.5,-80.7 57.5,-83.2 57.5,-83.2 57.5,-83.2 57.5,-80.7 55.25,-83.2 57.5,-78.2 57.5,-78.2\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.33,-78C176.33,-78 130.67,-78 130.67,-78 127.83,-78 125,-75.17 125,-72.33 125,-72.33 125,-66.67 125,-66.67 125,-63.83 127.83,-61 130.67,-61 130.67,-61 176.33,-61 176.33,-61 179.17,-61 182,-63.83 182,-66.67 182,-66.67 182,-72.33 182,-72.33 182,-75.17 179.17,-78 176.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"129\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] $</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>1-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M74.02,-69.5C86.39,-69.5 104.14,-69.5 119.63,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"124.79,-69.5 119.79,-71.75 122.29,-69.5 119.79,-69.5 119.79,-69.5 119.79,-69.5 122.29,-69.5 119.79,-67.25 124.79,-69.5 124.79,-69.5\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M293.33,-78C293.33,-78 235.67,-78 235.67,-78 232.83,-78 230,-75.17 230,-72.33 230,-72.33 230,-66.67 230,-66.67 230,-63.83 232.83,-61 235.67,-61 235.67,-61 293.33,-61 293.33,-61 296.17,-61 299,-63.83 299,-66.67 299,-66.67 299,-72.33 299,-72.33 299,-75.17 296.17,-78 293.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"234\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] 0 $</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>2-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M182.01,-69.5C194.92,-69.5 210.55,-69.5 224.65,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"229.77,-69.5 224.77,-71.75 227.27,-69.5 224.77,-69.5 224.77,-69.5 224.77,-69.5 227.27,-69.5 224.77,-67.25 229.77,-69.5 229.77,-69.5\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M422.33,-78C422.33,-78 352.67,-78 352.67,-78 349.83,-78 347,-75.17 347,-72.33 347,-72.33 347,-66.67 347,-66.67 347,-63.83 349.83,-61 352.67,-61 352.67,-61 422.33,-61 422.33,-61 425.17,-61 428,-63.83 428,-66.67 428,-66.67 428,-72.33 428,-72.33 428,-75.17 425.17,-78 422.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"351\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] 0 0 …</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>3-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M299.21,-69.5C312.41,-69.5 327.75,-69.5 341.85,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"346.98,-69.5 341.98,-71.75 344.48,-69.5 341.98,-69.5 341.98,-69.5 341.98,-69.5 344.48,-69.5 341.98,-67.25 346.98,-69.5 346.98,-69.5\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M539.33,-78C539.33,-78 481.67,-78 481.67,-78 478.83,-78 476,-75.17 476,-72.33 476,-72.33 476,-66.67 476,-66.67 476,-63.83 478.83,-61 481.67,-61 481.67,-61 539.33,-61 539.33,-61 542.17,-61 545,-63.83 545,-66.67 545,-66.67 545,-72.33 545,-72.33 545,-75.17 542.17,-78 539.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"480\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] 0 $</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>4-&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M428.12,-69.5C441.75,-69.5 456.99,-69.5 470.57,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"475.88,-69.5 470.88,-71.75 473.38,-69.5 470.88,-69.5 470.88,-69.5 470.88,-69.5 473.38,-69.5 470.88,-67.25 475.88,-69.5 475.88,-69.5\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>7</title>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;7 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>5-&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M173.49,-157.5C191.85,-157.5 219.75,-157.5 239.61,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"244.73,-157.5 239.73,-159.75 242.23,-157.5 239.73,-157.5 239.73,-157.5 239.73,-157.5 242.23,-157.5 239.73,-155.25 244.73,-157.5 244.73,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"203\" y=\"-163.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>6-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M77.07,-157.5C91.88,-157.5 112.71,-157.5 128.73,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"133.97,-157.5 128.97,-159.75 131.47,-157.5 128.97,-157.5 128.97,-157.5 128.97,-157.5 131.47,-157.5 128.97,-155.25 133.97,-157.5 133.97,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"98\" y=\"-163.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",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>7-&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M284.14,-157.5C305.22,-157.5 339.59,-157.5 362.62,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"367.64,-157.5 362.64,-159.75 365.14,-157.5 362.64,-157.5 362.64,-157.5 362.64,-157.5 365.14,-157.5 362.64,-155.25 367.64,-157.5 367.64,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"320\" y=\"-163.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>9</title>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>8-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M407.14,-157.5C428.22,-157.5 462.59,-157.5 485.62,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"490.64,-157.5 485.64,-159.75 488.14,-157.5 485.64,-157.5 485.64,-157.5 485.64,-157.5 488.14,-157.5 485.64,-155.25 490.64,-157.5 490.64,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"449\" y=\"-163.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>10</title>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>9-&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M530.49,-157.5C548.85,-157.5 576.75,-157.5 596.61,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"601.73,-157.5 596.73,-159.75 599.23,-157.5 596.73,-157.5 596.73,-157.5 596.73,-157.5 599.23,-157.5 596.73,-155.25 601.73,-157.5 601.73,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"566\" y=\"-163.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>11</title>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>10-&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M641.27,-157.5C656.23,-157.5 677.29,-157.5 693.48,-157.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"698.77,-157.5 693.77,-159.75 696.27,-157.5 693.77,-157.5 693.77,-157.5 693.77,-157.5 696.27,-157.5 693.77,-155.25 698.77,-157.5 698.77,-157.5\"/>\n",
       "<text text-anchor=\"start\" x=\"671\" y=\"-163.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",
       "<path fill=\"none\" stroke=\"black\" d=\"M644.33,-78C644.33,-78 598.67,-78 598.67,-78 595.83,-78 593,-75.17 593,-72.33 593,-72.33 593,-66.67 593,-66.67 593,-63.83 595.83,-61 598.67,-61 598.67,-61 644.33,-61 644.33,-61 647.17,-61 650,-63.83 650,-66.67 650,-66.67 650,-72.33 650,-72.33 650,-75.17 647.17,-78 644.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"597\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] $</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>12-&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M545.09,-69.5C558.57,-69.5 574.05,-69.5 587.47,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"592.69,-69.5 587.69,-71.75 590.19,-69.5 587.69,-69.5 587.69,-69.5 587.69,-69.5 590.19,-69.5 587.69,-67.25 592.69,-69.5 592.69,-69.5\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M729.33,-78C729.33,-78 707.67,-78 707.67,-78 704.83,-78 702,-75.17 702,-72.33 702,-72.33 702,-66.67 702,-66.67 702,-63.83 704.83,-61 707.67,-61 707.67,-61 729.33,-61 729.33,-61 732.17,-61 735,-63.83 735,-66.67 735,-66.67 735,-72.33 735,-72.33 735,-75.17 732.17,-78 729.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"706\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,$</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>13-&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M650.23,-69.5C665.03,-69.5 682.94,-69.5 696.55,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"701.73,-69.5 696.73,-71.75 699.23,-69.5 696.73,-69.5 696.73,-69.5 696.73,-69.5 699.23,-69.5 696.73,-67.25 701.73,-69.5 701.73,-69.5\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M729.33,-21C729.33,-21 707.67,-21 707.67,-21 704.83,-21 702,-18.17 702,-15.33 702,-15.33 702,-9.67 702,-9.67 702,-6.83 704.83,-4 707.67,-4 707.67,-4 729.33,-4 729.33,-4 732.17,-4 735,-6.83 735,-9.67 735,-9.67 735,-15.33 735,-15.33 735,-18.17 732.17,-21 729.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M730.67,-25C730.67,-25 706.33,-25 706.33,-25 702.17,-25 698,-20.83 698,-16.67 698,-16.67 698,-8.33 698,-8.33 698,-4.17 702.17,0 706.33,0 706.33,0 730.67,0 730.67,0 734.83,0 739,-4.17 739,-8.33 739,-8.33 739,-16.67 739,-16.67 739,-20.83 734.83,-25 730.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"706\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4,ε</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>14-&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M718.5,-60.89C718.5,-50.82 718.5,-40.75 718.5,-30.68\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"718.5,-25.41 720.75,-30.41 718.5,-27.91 718.5,-30.41 718.5,-30.41 718.5,-30.41 718.5,-27.91 716.25,-30.41 718.5,-25.41 718.5,-25.41\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, \"0 0 0 1 1 1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The nodes of the run now show the contents of the stack as well. The top symbol of the stack is marked with square brackets. If the stack gets too deep, then only the top few elements are shown, with an ellipsis instead of the rest of the stack. You can change how many stack elements are displayed using the `show_stack` option, which defaults to 3. (More about ellipses below.)\n",
    "\n",
    "This is a deterministic PDA. That's not very exciting, so let's try a nondeterministic PDA. This one (Example 2.18) accepts strings of the form $\\{ww^R\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, True, False)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = read_csv(\"examples/sipser-2-18.csv\")\n",
    "m.is_finite(), m.is_pushdown(), m.is_deterministic()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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\"></th>\n",
       "    <th style=\"text-align: left\">0</th>\n",
       "    <th style=\"text-align: left\"></th>\n",
       "    <th style=\"text-align: left\">1</th>\n",
       "    <th style=\"text-align: left\"></th>\n",
       "  </tr>\n",
       "  <tr>\n",
       "    <th style=\"text-align: left\"></th>\n",
       "    <th style=\"text-align: left\">ε</th>\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\">ε</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\">q2,$</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></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\"></td>\n",
       "    <td style=\"text-align: left\">q2,0</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q2,1</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\">q4,ε</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q3,ε</td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\">q3,ε</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\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "    <td style=\"text-align: left\"></td>\n",
       "  </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "<tock.tables.Table at 0x106df3d30>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_table(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"401pt\" height=\"77pt\" viewBox=\"0.00 0.00 401.00 77.00\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 73)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-73 397,-73 397,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.33,-21C57.33,-21 47.67,-21 47.67,-21 44.83,-21 42,-18.17 42,-15.33 42,-15.33 42,-9.67 42,-9.67 42,-6.83 44.83,-4 47.67,-4 47.67,-4 57.33,-4 57.33,-4 60.17,-4 63,-6.83 63,-9.67 63,-9.67 63,-15.33 63,-15.33 63,-18.17 60.17,-21 57.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M58.67,-25C58.67,-25 46.33,-25 46.33,-25 42.17,-25 38,-20.83 38,-16.67 38,-16.67 38,-8.33 38,-8.33 38,-4.17 42.17,0 46.33,0 46.33,0 58.67,0 58.67,0 62.83,0 67,-4.17 67,-8.33 67,-8.33 67,-16.67 67,-16.67 67,-20.83 62.83,-25 58.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"46\" 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.14,-12.5C2.84,-12.5 19.1,-12.5 32.69,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"37.92,-12.5 32.92,-14.75 35.42,-12.5 32.92,-12.5 32.92,-12.5 32.92,-12.5 35.42,-12.5 32.92,-10.25 37.92,-12.5 37.92,-12.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M165.83,-21C165.83,-21 156.17,-21 156.17,-21 153.33,-21 150.5,-18.17 150.5,-15.33 150.5,-15.33 150.5,-9.67 150.5,-9.67 150.5,-6.83 153.33,-4 156.17,-4 156.17,-4 165.83,-4 165.83,-4 168.67,-4 171.5,-6.83 171.5,-9.67 171.5,-9.67 171.5,-15.33 171.5,-15.33 171.5,-18.17 168.67,-21 165.83,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"154.5\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M152.95,-21.19C148.51,-29.67 151.19,-39 161,-39 168.97,-39 172.23,-32.84 170.79,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"169.05,-21.19 172.87,-25.11 169.9,-23.53 170.76,-25.88 170.76,-25.88 170.76,-25.88 169.9,-23.53 168.64,-26.65 169.05,-21.19 169.05,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"143\" y=\"-58.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">0,ε → 0</text>\n",
       "<text text-anchor=\"start\" x=\"143\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">1,ε → 1</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M274.83,-21C274.83,-21 265.17,-21 265.17,-21 262.33,-21 259.5,-18.17 259.5,-15.33 259.5,-15.33 259.5,-9.67 259.5,-9.67 259.5,-6.83 262.33,-4 265.17,-4 265.17,-4 274.83,-4 274.83,-4 277.67,-4 280.5,-6.83 280.5,-9.67 280.5,-9.67 280.5,-15.33 280.5,-15.33 280.5,-18.17 277.67,-21 274.83,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"263.5\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M171.87,-12.5C190.76,-12.5 232.09,-12.5 254.26,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"259.46,-12.5 254.46,-14.75 256.96,-12.5 254.46,-12.5 254.46,-12.5 254.46,-12.5 256.96,-12.5 254.46,-10.25 259.46,-12.5 259.46,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"197.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,ε → ε</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M261.95,-21.19C257.51,-29.67 260.19,-39 270,-39 277.97,-39 281.23,-32.84 279.79,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"278.05,-21.19 281.87,-25.11 278.9,-23.53 279.76,-25.88 279.76,-25.88 279.76,-25.88 278.9,-23.53 277.64,-26.65 278.05,-21.19 278.05,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"252\" y=\"-58.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">0,0 → ε</text>\n",
       "<text text-anchor=\"start\" x=\"252\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">1,1 → ε</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M383.33,-21C383.33,-21 373.67,-21 373.67,-21 370.83,-21 368,-18.17 368,-15.33 368,-15.33 368,-9.67 368,-9.67 368,-6.83 370.83,-4 373.67,-4 373.67,-4 383.33,-4 383.33,-4 386.17,-4 389,-6.83 389,-9.67 389,-9.67 389,-15.33 389,-15.33 389,-18.17 386.17,-21 383.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.67,-25C384.67,-25 372.33,-25 372.33,-25 368.17,-25 364,-20.83 364,-16.67 364,-16.67 364,-8.33 364,-8.33 364,-4.17 368.17,0 372.33,0 372.33,0 384.67,0 384.67,0 388.83,0 393,-4.17 393,-8.33 393,-8.33 393,-16.67 393,-16.67 393,-20.83 388.83,-25 384.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"372\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>1-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M280.83,-12.5C298.47,-12.5 335.77,-12.5 358.54,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"363.71,-12.5 358.71,-14.75 361.21,-12.5 358.71,-12.5 358.71,-12.5 358.71,-12.5 361.21,-12.5 358.71,-10.25 363.71,-12.5 363.71,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"306.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,$ → ε</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=\"M67.42,-12.5C87.61,-12.5 124.83,-12.5 145.39,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"150.48,-12.5 145.48,-14.75 147.98,-12.5 145.48,-12.5 145.48,-12.5 145.48,-12.5 147.98,-12.5 145.48,-10.25 150.48,-12.5 150.48,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"88.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,ε → $</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": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"823pt\" height=\"261pt\" viewBox=\"0.00 0.00 823.00 260.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256.5 819,-256.5 819,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-206C68.33,-206 46.67,-206 46.67,-206 43.83,-206 41,-203.17 41,-200.33 41,-200.33 41,-194.67 41,-194.67 41,-191.83 43.83,-189 46.67,-189 46.67,-189 68.33,-189 68.33,-189 71.17,-189 74,-191.83 74,-194.67 74,-194.67 74,-200.33 74,-200.33 74,-203.17 71.17,-206 68.33,-206\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-195\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1,ε</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.16,-197.5C3.01,-197.5 20.55,-197.5 35.4,-197.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"40.72,-197.5 35.72,-199.75 38.22,-197.5 35.72,-197.5 35.72,-197.5 35.72,-197.5 38.22,-197.5 35.72,-195.25 40.72,-197.5 40.72,-197.5\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-153C68.33,-153 46.67,-153 46.67,-153 43.83,-153 41,-150.17 41,-147.33 41,-147.33 41,-141.67 41,-141.67 41,-138.83 43.83,-136 46.67,-136 46.67,-136 68.33,-136 68.33,-136 71.17,-136 74,-138.83 74,-141.67 74,-141.67 74,-147.33 74,-147.33 74,-150.17 71.17,-153 68.33,-153\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-142\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,$</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>0-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.5,-188.85C57.5,-178.63 57.5,-168.42 57.5,-158.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.5,-153.2 59.75,-158.2 57.5,-155.7 57.5,-158.2 57.5,-158.2 57.5,-158.2 57.5,-155.7 55.25,-158.2 57.5,-153.2 57.5,-153.2\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.33,-153C176.33,-153 130.67,-153 130.67,-153 127.83,-153 125,-150.17 125,-147.33 125,-147.33 125,-141.67 125,-141.67 125,-138.83 127.83,-136 130.67,-136 130.67,-136 176.33,-136 176.33,-136 179.17,-136 182,-138.83 182,-141.67 182,-141.67 182,-147.33 182,-147.33 182,-150.17 179.17,-153 176.33,-153\"/>\n",
       "<text text-anchor=\"start\" x=\"129\" y=\"-142\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] $</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>1-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M74.02,-144.5C86.39,-144.5 104.14,-144.5 119.63,-144.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"124.79,-144.5 119.79,-146.75 122.29,-144.5 119.79,-144.5 119.79,-144.5 119.79,-144.5 122.29,-144.5 119.79,-142.25 124.79,-144.5 124.79,-144.5\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-100C68.33,-100 46.67,-100 46.67,-100 43.83,-100 41,-97.17 41,-94.33 41,-94.33 41,-88.67 41,-88.67 41,-85.83 43.83,-83 46.67,-83 46.67,-83 68.33,-83 68.33,-83 71.17,-83 74,-85.83 74,-88.67 74,-88.67 74,-94.33 74,-94.33 74,-97.17 71.17,-100 68.33,-100\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-89\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,$</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>1-&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.5,-135.85C57.5,-125.63 57.5,-115.42 57.5,-105.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.5,-100.2 59.75,-105.2 57.5,-102.7 57.5,-105.2 57.5,-105.2 57.5,-105.2 57.5,-102.7 55.25,-105.2 57.5,-100.2 57.5,-100.2\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M77.07,-236.5C91.88,-236.5 112.71,-236.5 128.73,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"133.97,-236.5 128.97,-238.75 131.47,-236.5 128.97,-236.5 128.97,-236.5 128.97,-236.5 131.47,-236.5 128.97,-234.25 133.97,-236.5 133.97,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"98\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>7</title>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;7 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3-&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M536.24,-236.5C558.66,-236.5 596.22,-236.5 620.67,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"625.68,-236.5 620.68,-238.75 623.18,-236.5 620.68,-236.5 620.68,-236.5 620.68,-236.5 623.18,-236.5 620.68,-234.25 625.68,-236.5 625.68,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"578\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>4-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M173.49,-236.5C191.85,-236.5 219.75,-236.5 239.61,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"244.73,-236.5 239.73,-238.75 242.23,-236.5 239.73,-236.5 239.73,-236.5 239.73,-236.5 242.23,-236.5 239.73,-234.25 244.73,-236.5 244.73,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"203\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>5-&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M284.14,-236.5C305.22,-236.5 339.59,-236.5 362.62,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"367.64,-236.5 362.64,-238.75 365.14,-236.5 362.64,-236.5 362.64,-236.5 362.64,-236.5 365.14,-236.5 362.64,-234.25 367.64,-236.5 367.64,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"320\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>6-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M407.24,-236.5C429.66,-236.5 467.22,-236.5 491.67,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"496.68,-236.5 491.68,-238.75 494.18,-236.5 491.68,-236.5 491.68,-236.5 491.68,-236.5 494.18,-236.5 491.68,-234.25 496.68,-236.5 496.68,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"449\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">1</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>8</title>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>7-&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M665.24,-236.5C687.66,-236.5 725.22,-236.5 749.67,-236.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"754.68,-236.5 749.68,-238.75 752.18,-236.5 749.68,-236.5 749.68,-236.5 749.68,-236.5 752.18,-236.5 749.68,-234.25 754.68,-236.5 754.68,-236.5\"/>\n",
       "<text text-anchor=\"start\" x=\"707\" y=\"-242.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M293.33,-159C293.33,-159 235.67,-159 235.67,-159 232.83,-159 230,-156.17 230,-153.33 230,-153.33 230,-147.67 230,-147.67 230,-144.83 232.83,-142 235.67,-142 235.67,-142 293.33,-142 293.33,-142 296.17,-142 299,-144.83 299,-147.67 299,-147.67 299,-153.33 299,-153.33 299,-156.17 296.17,-159 293.33,-159\"/>\n",
       "<text text-anchor=\"start\" x=\"234\" y=\"-148\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] 0 $</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>9-&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M182.01,-146.01C194.92,-146.73 210.55,-147.59 224.65,-148.36\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"229.77,-148.64 224.65,-150.61 227.27,-148.51 224.78,-148.37 224.78,-148.37 224.78,-148.37 227.27,-148.51 224.9,-146.12 229.77,-148.64 229.77,-148.64\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.33,-91C176.33,-91 130.67,-91 130.67,-91 127.83,-91 125,-88.17 125,-85.33 125,-85.33 125,-79.67 125,-79.67 125,-76.83 127.83,-74 130.67,-74 130.67,-74 176.33,-74 176.33,-74 179.17,-74 182,-76.83 182,-79.67 182,-79.67 182,-85.33 182,-85.33 182,-88.17 179.17,-91 176.33,-91\"/>\n",
       "<text text-anchor=\"start\" x=\"129\" y=\"-80\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] $</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>9-&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M153.5,-135.76C153.5,-122.65 153.5,-109.55 153.5,-96.44\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"153.5,-91.22 155.75,-96.22 153.5,-93.72 153.5,-96.22 153.5,-96.22 153.5,-96.22 153.5,-93.72 151.25,-96.22 153.5,-91.22 153.5,-91.22\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.33,-47C68.33,-47 46.67,-47 46.67,-47 43.83,-47 41,-44.17 41,-41.33 41,-41.33 41,-35.67 41,-35.67 41,-32.83 43.83,-30 46.67,-30 46.67,-30 68.33,-30 68.33,-30 71.17,-30 74,-32.83 74,-35.67 74,-35.67 74,-41.33 74,-41.33 74,-44.17 71.17,-47 68.33,-47\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-36\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4,ε</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;13 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>10-&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.5,-82.85C57.5,-72.63 57.5,-62.42 57.5,-52.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.5,-47.2 59.75,-52.2 57.5,-49.7 57.5,-52.2 57.5,-52.2 57.5,-52.2 57.5,-49.7 55.25,-52.2 57.5,-47.2 57.5,-47.2\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M293.33,-106C293.33,-106 235.67,-106 235.67,-106 232.83,-106 230,-103.17 230,-100.33 230,-100.33 230,-94.67 230,-94.67 230,-91.83 232.83,-89 235.67,-89 235.67,-89 293.33,-89 293.33,-89 296.17,-89 299,-91.83 299,-94.67 299,-94.67 299,-100.33 299,-100.33 299,-103.17 296.17,-106 293.33,-106\"/>\n",
       "<text text-anchor=\"start\" x=\"234\" y=\"-95\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] 0 $</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;14 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>11-&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M264.5,-141.85C264.5,-131.63 264.5,-121.42 264.5,-111.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"264.5,-106.2 266.75,-111.2 264.5,-108.7 264.5,-111.2 264.5,-111.2 264.5,-111.2 264.5,-108.7 262.25,-111.2 264.5,-106.2 264.5,-106.2\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M422.33,-159C422.33,-159 352.67,-159 352.67,-159 349.83,-159 347,-156.17 347,-153.33 347,-153.33 347,-147.67 347,-147.67 347,-144.83 349.83,-142 352.67,-142 352.67,-142 422.33,-142 422.33,-142 425.17,-142 428,-144.83 428,-147.67 428,-147.67 428,-153.33 428,-153.33 428,-156.17 425.17,-159 422.33,-159\"/>\n",
       "<text text-anchor=\"start\" x=\"351\" y=\"-148\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[1] 0 0 …</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;16 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>11-&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M299.21,-150.5C312.41,-150.5 327.75,-150.5 341.85,-150.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"346.98,-150.5 341.98,-152.75 344.48,-150.5 341.98,-150.5 341.98,-150.5 341.98,-150.5 344.48,-150.5 341.98,-148.25 346.98,-150.5 346.98,-150.5\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M275.33,-71C275.33,-71 253.67,-71 253.67,-71 250.83,-71 248,-68.17 248,-65.33 248,-65.33 248,-59.67 248,-59.67 248,-56.83 250.83,-54 253.67,-54 253.67,-54 275.33,-54 275.33,-54 278.17,-54 281,-56.83 281,-59.67 281,-59.67 281,-65.33 281,-65.33 281,-68.17 278.17,-71 275.33,-71\"/>\n",
       "<text text-anchor=\"start\" x=\"252\" y=\"-60\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,$</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;15 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>12-&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M182.01,-77.45C200.87,-73.99 225.5,-69.47 242.72,-66.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"247.82,-65.38 243.31,-68.49 245.36,-65.83 242.9,-66.28 242.9,-66.28 242.9,-66.28 245.36,-65.83 242.49,-64.07 247.82,-65.38 247.82,-65.38\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M275.33,-18C275.33,-18 253.67,-18 253.67,-18 250.83,-18 248,-15.17 248,-12.33 248,-12.33 248,-6.67 248,-6.67 248,-3.83 250.83,-1 253.67,-1 253.67,-1 275.33,-1 275.33,-1 278.17,-1 281,-3.83 281,-6.67 281,-6.67 281,-12.33 281,-12.33 281,-15.17 278.17,-18 275.33,-18\"/>\n",
       "<text text-anchor=\"start\" x=\"252\" y=\"-7\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4,ε</text>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;17 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>15-&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M264.5,-53.85C264.5,-43.63 264.5,-33.42 264.5,-23.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"264.5,-18.2 266.75,-23.2 264.5,-20.7 264.5,-23.2 264.5,-23.2 264.5,-23.2 264.5,-20.7 262.25,-23.2 264.5,-18.2 264.5,-18.2\"/>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node20\" class=\"node\">\n",
       "<title>18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M422.33,-102C422.33,-102 352.67,-102 352.67,-102 349.83,-102 347,-99.17 347,-96.33 347,-96.33 347,-90.67 347,-90.67 347,-87.83 349.83,-85 352.67,-85 352.67,-85 422.33,-85 422.33,-85 425.17,-85 428,-87.83 428,-90.67 428,-90.67 428,-96.33 428,-96.33 428,-99.17 425.17,-102 422.33,-102\"/>\n",
       "<text text-anchor=\"start\" x=\"351\" y=\"-91\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[1] 0 0 …</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;18 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>16-&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M387.5,-141.86C387.5,-130.45 387.5,-119.05 387.5,-107.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"387.5,-102.41 389.75,-107.41 387.5,-104.91 387.5,-107.41 387.5,-107.41 387.5,-107.41 387.5,-104.91 385.25,-107.41 387.5,-102.41 387.5,-102.41\"/>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node21\" class=\"node\">\n",
       "<title>19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M551.33,-166C551.33,-166 481.67,-166 481.67,-166 478.83,-166 476,-163.17 476,-160.33 476,-160.33 476,-154.67 476,-154.67 476,-151.83 478.83,-149 481.67,-149 481.67,-149 551.33,-149 551.33,-149 554.17,-149 557,-151.83 557,-154.67 557,-154.67 557,-160.33 557,-160.33 557,-163.17 554.17,-166 551.33,-166\"/>\n",
       "<text text-anchor=\"start\" x=\"480\" y=\"-155\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[1] 1 0 …</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;19 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>16-&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M428.34,-152.7C441.81,-153.44 456.95,-154.27 470.78,-155.03\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"475.81,-155.31 470.69,-157.28 473.31,-155.17 470.81,-155.04 470.81,-155.04 470.81,-155.04 473.31,-155.17 470.94,-152.79 475.81,-155.31 475.81,-155.31\"/>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node23\" class=\"node\">\n",
       "<title>21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M545.33,-78C545.33,-78 487.67,-78 487.67,-78 484.83,-78 482,-75.17 482,-72.33 482,-72.33 482,-66.67 482,-66.67 482,-63.83 484.83,-61 487.67,-61 487.67,-61 545.33,-61 545.33,-61 548.17,-61 551,-63.83 551,-66.67 551,-66.67 551,-72.33 551,-72.33 551,-75.17 548.17,-78 545.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"486\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] 0 $</text>\n",
       "</g>\n",
       "<!-- 18&#45;&gt;21 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>18-&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M428.34,-85.97C443.76,-83.06 461.36,-79.73 476.68,-76.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"481.79,-75.87 477.29,-79.01 479.33,-76.34 476.87,-76.8 476.87,-76.8 476.87,-76.8 479.33,-76.34 476.46,-74.59 481.79,-75.87 481.79,-75.87\"/>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node22\" class=\"node\">\n",
       "<title>20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M551.33,-113C551.33,-113 481.67,-113 481.67,-113 478.83,-113 476,-110.17 476,-107.33 476,-107.33 476,-101.67 476,-101.67 476,-98.83 478.83,-96 481.67,-96 481.67,-96 551.33,-96 551.33,-96 554.17,-96 557,-98.83 557,-101.67 557,-101.67 557,-107.33 557,-107.33 557,-110.17 554.17,-113 551.33,-113\"/>\n",
       "<text text-anchor=\"start\" x=\"480\" y=\"-102\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[1] 1 0 …</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>19-&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M516.5,-148.85C516.5,-138.63 516.5,-128.42 516.5,-118.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"516.5,-113.2 518.75,-118.2 516.5,-115.7 516.5,-118.2 516.5,-118.2 516.5,-118.2 516.5,-115.7 514.25,-118.2 516.5,-113.2 516.5,-113.2\"/>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node24\" class=\"node\">\n",
       "<title>22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M680.33,-166C680.33,-166 610.67,-166 610.67,-166 607.83,-166 605,-163.17 605,-160.33 605,-160.33 605,-154.67 605,-154.67 605,-151.83 607.83,-149 610.67,-149 610.67,-149 680.33,-149 680.33,-149 683.17,-149 686,-151.83 686,-154.67 686,-154.67 686,-160.33 686,-160.33 686,-163.17 683.17,-166 680.33,-166\"/>\n",
       "<text text-anchor=\"start\" x=\"609\" y=\"-155\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] 1 1 …</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;22 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>19-&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M557.34,-157.5C570.81,-157.5 585.95,-157.5 599.78,-157.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"604.81,-157.5 599.81,-159.75 602.31,-157.5 599.81,-157.5 599.81,-157.5 599.81,-157.5 602.31,-157.5 599.81,-155.25 604.81,-157.5 604.81,-157.5\"/>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node25\" class=\"node\">\n",
       "<title>23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M668.33,-78C668.33,-78 622.67,-78 622.67,-78 619.83,-78 617,-75.17 617,-72.33 617,-72.33 617,-66.67 617,-66.67 617,-63.83 619.83,-61 622.67,-61 622.67,-61 668.33,-61 668.33,-61 671.17,-61 674,-63.83 674,-66.67 674,-66.67 674,-72.33 674,-72.33 674,-75.17 671.17,-78 668.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"621\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] $</text>\n",
       "</g>\n",
       "<!-- 21&#45;&gt;23 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>21-&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M551.2,-69.5C569.87,-69.5 592.99,-69.5 611.55,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"616.65,-69.5 611.65,-71.75 614.15,-69.5 611.65,-69.5 611.65,-69.5 611.65,-69.5 614.15,-69.5 611.65,-67.25 616.65,-69.5 616.65,-69.5\"/>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node26\" class=\"node\">\n",
       "<title>24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M680.33,-113C680.33,-113 610.67,-113 610.67,-113 607.83,-113 605,-110.17 605,-107.33 605,-107.33 605,-101.67 605,-101.67 605,-98.83 607.83,-96 610.67,-96 610.67,-96 680.33,-96 680.33,-96 683.17,-96 686,-98.83 686,-101.67 686,-101.67 686,-107.33 686,-107.33 686,-110.17 683.17,-113 680.33,-113\"/>\n",
       "<text text-anchor=\"start\" x=\"609\" y=\"-102\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] 1 1 …</text>\n",
       "</g>\n",
       "<!-- 22&#45;&gt;24 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>22-&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M645.5,-148.85C645.5,-138.63 645.5,-128.42 645.5,-118.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"645.5,-113.2 647.75,-118.2 645.5,-115.7 645.5,-118.2 645.5,-118.2 645.5,-118.2 645.5,-115.7 643.25,-118.2 645.5,-113.2 645.5,-113.2\"/>\n",
       "</g>\n",
       "<!-- 26 -->\n",
       "<g id=\"node28\" class=\"node\">\n",
       "<title>26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M809.33,-201C809.33,-201 739.67,-201 739.67,-201 736.83,-201 734,-198.17 734,-195.33 734,-195.33 734,-189.67 734,-189.67 734,-186.83 736.83,-184 739.67,-184 739.67,-184 809.33,-184 809.33,-184 812.17,-184 815,-186.83 815,-189.67 815,-189.67 815,-195.33 815,-195.33 815,-198.17 812.17,-201 809.33,-201\"/>\n",
       "<text text-anchor=\"start\" x=\"738\" y=\"-190\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[0] 0 1 …</text>\n",
       "</g>\n",
       "<!-- 22&#45;&gt;26 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>22-&gt;26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M677.57,-166.06C695.56,-171.02 718.29,-177.29 737.11,-182.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"742.31,-183.91 736.89,-184.75 739.9,-183.24 737.49,-182.58 737.49,-182.58 737.49,-182.58 739.9,-183.24 738.09,-180.41 742.31,-183.91 742.31,-183.91\"/>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node27\" class=\"node\">\n",
       "<title>25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M785.33,-78C785.33,-78 763.67,-78 763.67,-78 760.83,-78 758,-75.17 758,-72.33 758,-72.33 758,-66.67 758,-66.67 758,-63.83 760.83,-61 763.67,-61 763.67,-61 785.33,-61 785.33,-61 788.17,-61 791,-63.83 791,-66.67 791,-66.67 791,-72.33 791,-72.33 791,-75.17 788.17,-78 785.33,-78\"/>\n",
       "<text text-anchor=\"start\" x=\"762\" y=\"-67\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,$</text>\n",
       "</g>\n",
       "<!-- 23&#45;&gt;25 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>23-&gt;25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M674.06,-69.5C697.73,-69.5 731.34,-69.5 752.78,-69.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"757.96,-69.5 752.96,-71.75 755.46,-69.5 752.96,-69.5 752.96,-69.5 752.96,-69.5 755.46,-69.5 752.96,-67.25 757.96,-69.5 757.96,-69.5\"/>\n",
       "</g>\n",
       "<!-- 29 -->\n",
       "<g id=\"node31\" class=\"node\">\n",
       "<title>29</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M809.33,-113C809.33,-113 739.67,-113 739.67,-113 736.83,-113 734,-110.17 734,-107.33 734,-107.33 734,-101.67 734,-101.67 734,-98.83 736.83,-96 739.67,-96 739.67,-96 809.33,-96 809.33,-96 812.17,-96 815,-98.83 815,-101.67 815,-101.67 815,-107.33 815,-107.33 815,-110.17 812.17,-113 809.33,-113\"/>\n",
       "<text text-anchor=\"start\" x=\"738\" y=\"-102\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[1] 1 0 …</text>\n",
       "</g>\n",
       "<!-- 24&#45;&gt;29 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>24-&gt;29</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M686.34,-104.5C699.81,-104.5 714.95,-104.5 728.78,-104.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"733.81,-104.5 728.81,-106.75 731.31,-104.5 728.81,-104.5 728.81,-104.5 728.81,-104.5 731.31,-104.5 728.81,-102.25 733.81,-104.5 733.81,-104.5\"/>\n",
       "</g>\n",
       "<!-- 27 -->\n",
       "<g id=\"node29\" class=\"node\">\n",
       "<title>27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M785.33,-21C785.33,-21 763.67,-21 763.67,-21 760.83,-21 758,-18.17 758,-15.33 758,-15.33 758,-9.67 758,-9.67 758,-6.83 760.83,-4 763.67,-4 763.67,-4 785.33,-4 785.33,-4 788.17,-4 791,-6.83 791,-9.67 791,-9.67 791,-15.33 791,-15.33 791,-18.17 788.17,-21 785.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M786.67,-25C786.67,-25 762.33,-25 762.33,-25 758.17,-25 754,-20.83 754,-16.67 754,-16.67 754,-8.33 754,-8.33 754,-4.17 758.17,0 762.33,0 762.33,0 786.67,0 786.67,0 790.83,0 795,-4.17 795,-8.33 795,-8.33 795,-16.67 795,-16.67 795,-20.83 790.83,-25 786.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"762\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4,ε</text>\n",
       "</g>\n",
       "<!-- 25&#45;&gt;27 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>25-&gt;27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M774.5,-60.89C774.5,-50.82 774.5,-40.75 774.5,-30.68\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"774.5,-25.41 776.75,-30.41 774.5,-27.91 774.5,-30.41 774.5,-30.41 774.5,-30.41 774.5,-27.91 772.25,-30.41 774.5,-25.41 774.5,-25.41\"/>\n",
       "</g>\n",
       "<!-- 28 -->\n",
       "<g id=\"node30\" class=\"node\">\n",
       "<title>28</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M809.33,-148C809.33,-148 739.67,-148 739.67,-148 736.83,-148 734,-145.17 734,-142.33 734,-142.33 734,-136.67 734,-136.67 734,-133.83 736.83,-131 739.67,-131 739.67,-131 809.33,-131 809.33,-131 812.17,-131 815,-133.83 815,-136.67 815,-136.67 815,-142.33 815,-142.33 815,-145.17 812.17,-148 809.33,-148\"/>\n",
       "<text text-anchor=\"start\" x=\"738\" y=\"-137\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[0] 0 1 …</text>\n",
       "</g>\n",
       "<!-- 26&#45;&gt;28 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>26-&gt;28</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M774.5,-183.85C774.5,-173.63 774.5,-163.42 774.5,-153.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"774.5,-148.2 776.75,-153.2 774.5,-150.7 774.5,-153.2 774.5,-153.2 774.5,-153.2 774.5,-150.7 772.25,-153.2 774.5,-148.2 774.5,-148.2\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, \"0 0 1 1 0 0\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the nondeterminism: at every step, the automaton considers whether it might be at the midpoint of the string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We saw that in a nondeterministic FA, there could be infinitely many runs for an input string, and the run graph indicated this using a cycle. With nondeterministic PDAs, we have a new problem: they can push/pop as many times as they want without reading in any input, so the infinitely many runs also go through infinitely many configurations! Consider the following PDA, which (for some reason) pushes an arbitrary number of `#` signs, reads in a single `0`, then pops all the `#` signs again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"375pt\" height=\"63pt\" viewBox=\"0.00 0.00 375.00 63.00\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 59)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-59 371,-59 371,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.33,-21C53.33,-21 43.67,-21 43.67,-21 40.83,-21 38,-18.17 38,-15.33 38,-15.33 38,-9.67 38,-9.67 38,-6.83 40.83,-4 43.67,-4 43.67,-4 53.33,-4 53.33,-4 56.17,-4 59,-6.83 59,-9.67 59,-9.67 59,-15.33 59,-15.33 59,-18.17 56.17,-21 53.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"42\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.13,-12.5C2.79,-12.5 19.6,-12.5 32.5,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"37.74,-12.5 32.74,-14.75 35.24,-12.5 32.74,-12.5 32.74,-12.5 32.74,-12.5 35.24,-12.5 32.74,-10.25 37.74,-12.5 37.74,-12.5\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M153.33,-21C153.33,-21 143.67,-21 143.67,-21 140.83,-21 138,-18.17 138,-15.33 138,-15.33 138,-9.67 138,-9.67 138,-6.83 140.83,-4 143.67,-4 143.67,-4 153.33,-4 153.33,-4 156.17,-4 159,-6.83 159,-9.67 159,-9.67 159,-15.33 159,-15.33 159,-18.17 156.17,-21 153.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"142\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59.25,-12.5C76.5,-12.5 112.46,-12.5 132.75,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"137.78,-12.5 132.78,-14.75 135.28,-12.5 132.78,-12.5 132.78,-12.5 132.78,-12.5 135.28,-12.5 132.78,-10.25 137.78,-12.5 137.78,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"80.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,ε → $</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1-&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M141.05,-21.19C136.93,-29.67 139.42,-39 148.5,-39 155.88,-39 158.9,-32.84 157.57,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"155.95,-21.19 159.68,-25.2 156.75,-23.55 157.55,-25.92 157.55,-25.92 157.55,-25.92 156.75,-23.55 155.42,-26.64 155.95,-21.19 155.95,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"130.5\" y=\"-44.8\" 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=\"M253.33,-21C253.33,-21 243.67,-21 243.67,-21 240.83,-21 238,-18.17 238,-15.33 238,-15.33 238,-9.67 238,-9.67 238,-6.83 240.83,-4 243.67,-4 243.67,-4 253.33,-4 253.33,-4 256.17,-4 259,-6.83 259,-9.67 259,-9.67 259,-15.33 259,-15.33 259,-18.17 256.17,-21 253.33,-21\"/>\n",
       "<text text-anchor=\"start\" x=\"242\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.25,-12.5C176.5,-12.5 212.46,-12.5 232.75,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"237.78,-12.5 232.78,-14.75 235.28,-12.5 232.78,-12.5 232.78,-12.5 232.78,-12.5 235.28,-12.5 232.78,-10.25 237.78,-12.5 237.78,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"180.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0,ε → ε</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M241.05,-21.19C236.93,-29.67 239.42,-39 248.5,-39 255.88,-39 258.9,-32.84 257.57,-25.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"255.95,-21.19 259.68,-25.2 256.75,-23.55 257.55,-25.92 257.55,-25.92 257.55,-25.92 256.75,-23.55 255.42,-26.64 255.95,-21.19 255.95,-21.19\"/>\n",
       "<text text-anchor=\"start\" x=\"230.5\" y=\"-44.8\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,# → ε</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M357.33,-21C357.33,-21 347.67,-21 347.67,-21 344.83,-21 342,-18.17 342,-15.33 342,-15.33 342,-9.67 342,-9.67 342,-6.83 344.83,-4 347.67,-4 347.67,-4 357.33,-4 357.33,-4 360.17,-4 363,-6.83 363,-9.67 363,-9.67 363,-15.33 363,-15.33 363,-18.17 360.17,-21 357.33,-21\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.67,-25C358.67,-25 346.33,-25 346.33,-25 342.17,-25 338,-20.83 338,-16.67 338,-16.67 338,-8.33 338,-8.33 338,-4.17 342.17,0 346.33,0 346.33,0 358.67,0 358.67,0 362.83,0 367,-4.17 367,-8.33 367,-8.33 367,-16.67 367,-16.67 367,-20.83 362.83,-25 358.67,-25\"/>\n",
       "<text text-anchor=\"start\" x=\"346\" y=\"-10\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>2-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M259.28,-12.5C276.1,-12.5 310.8,-12.5 332.51,-12.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"337.73,-12.5 332.73,-14.75 335.23,-12.5 332.73,-12.5 332.73,-12.5 332.73,-12.5 335.23,-12.5 332.73,-10.25 337.73,-12.5 337.73,-12.5\"/>\n",
       "<text text-anchor=\"start\" x=\"280.5\" y=\"-18.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">ε,$ → ε</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "m = read_csv(\"examples/pdaloop.csv\")\n",
    "to_graph(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"256pt\" height=\"319pt\" viewBox=\"0.00 0.00 256.00 318.50\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 314.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-314.5 252,-314.5 252,4 -4,4\"/>\n",
       "<!-- _START -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M89.33,-268C89.33,-268 67.67,-268 67.67,-268 64.83,-268 62,-265.17 62,-262.33 62,-262.33 62,-256.67 62,-256.67 62,-253.83 64.83,-251 67.67,-251 67.67,-251 89.33,-251 89.33,-251 92.17,-251 95,-253.83 95,-256.67 95,-256.67 95,-262.33 95,-262.33 95,-265.17 92.17,-268 89.33,-268\"/>\n",
       "<text text-anchor=\"start\" x=\"66\" y=\"-257\" font-family=\"Courier,monospace\" font-size=\"10.00\">q1,ε</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;7 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>_START-&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1.06,-259.5C2.56,-259.5 34.5,-259.5 56.61,-259.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"61.72,-259.5 56.72,-261.75 59.22,-259.5 56.72,-259.5 56.72,-259.5 56.72,-259.5 59.22,-259.5 56.72,-257.25 61.72,-259.5 61.72,-259.5\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>0</title>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>1</title>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1-&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"white\" d=\"M98.24,-294.5C120.66,-294.5 158.22,-294.5 182.67,-294.5\"/>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"187.68,-294.5 182.68,-296.75 185.18,-294.5 182.68,-294.5 182.68,-294.5 182.68,-294.5 185.18,-294.5 182.68,-292.25 187.68,-294.5 187.68,-294.5\"/>\n",
       "<text text-anchor=\"start\" x=\"140\" y=\"-300.3\" font-family=\"Courier,monospace\" font-size=\"9.00\">0</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M218.33,-180C218.33,-180 196.67,-180 196.67,-180 193.83,-180 191,-177.17 191,-174.33 191,-174.33 191,-168.67 191,-168.67 191,-165.83 193.83,-163 196.67,-163 196.67,-163 218.33,-163 218.33,-163 221.17,-163 224,-165.83 224,-168.67 224,-168.67 224,-174.33 224,-174.33 224,-177.17 221.17,-180 218.33,-180\"/>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M219.67,-184C219.67,-184 195.33,-184 195.33,-184 191.17,-184 187,-179.83 187,-175.67 187,-175.67 187,-167.33 187,-167.33 187,-163.17 191.17,-159 195.33,-159 195.33,-159 219.67,-159 219.67,-159 223.83,-159 228,-163.17 228,-167.33 228,-167.33 228,-175.67 228,-175.67 228,-179.83 223.83,-184 219.67,-184\"/>\n",
       "<text text-anchor=\"start\" x=\"195\" y=\"-169\" font-family=\"Courier,monospace\" font-size=\"10.00\">q4,ε</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M113.33,-17C113.33,-17 43.67,-17 43.67,-17 40.83,-17 38,-14.17 38,-11.33 38,-11.33 38,-5.67 38,-5.67 38,-2.83 40.83,0 43.67,0 43.67,0 113.33,0 113.33,0 116.17,0 119,-2.83 119,-5.67 119,-5.67 119,-11.33 119,-11.33 119,-14.17 116.17,-17 113.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"42\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[#] # # …</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>3-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.86,-17.19C65.08,-25.67 67.96,-35 78.5,-35 87.06,-35 90.57,-28.84 89.02,-21.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"87.14,-17.19 91.06,-21.02 88.05,-19.51 88.97,-21.84 88.97,-21.84 88.97,-21.84 88.05,-19.51 86.87,-22.66 87.14,-17.19 87.14,-17.19\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.33,-17C242.33,-17 172.67,-17 172.67,-17 169.83,-17 167,-14.17 167,-11.33 167,-11.33 167,-5.67 167,-5.67 167,-2.83 169.83,0 172.67,0 172.67,0 242.33,0 242.33,0 245.17,0 248,-2.83 248,-5.67 248,-5.67 248,-11.33 248,-11.33 248,-14.17 245.17,-17 242.33,-17\"/>\n",
       "<text text-anchor=\"start\" x=\"171\" y=\"-6\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[#] # # …</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>3-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M119.34,-8.5C132.81,-8.5 147.95,-8.5 161.78,-8.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.81,-8.5 161.81,-10.75 164.31,-8.5 161.81,-8.5 161.81,-8.5 161.81,-8.5 164.31,-8.5 161.81,-6.25 166.81,-8.5 166.81,-8.5\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-88C236.33,-88 178.67,-88 178.67,-88 175.83,-88 173,-85.17 173,-82.33 173,-82.33 173,-76.67 173,-76.67 173,-73.83 175.83,-71 178.67,-71 178.67,-71 236.33,-71 236.33,-71 239.17,-71 242,-73.83 242,-76.67 242,-76.67 242,-82.33 242,-82.33 242,-85.17 239.17,-88 236.33,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"177\" y=\"-77\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[#] # $</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M230.33,-141C230.33,-141 184.67,-141 184.67,-141 181.83,-141 179,-138.17 179,-135.33 179,-135.33 179,-129.67 179,-129.67 179,-126.83 181.83,-124 184.67,-124 184.67,-124 230.33,-124 230.33,-124 233.17,-124 236,-126.83 236,-129.67 236,-129.67 236,-135.33 236,-135.33 236,-138.17 233.17,-141 230.33,-141\"/>\n",
       "<text text-anchor=\"start\" x=\"183\" y=\"-130\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,[#] $</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;11 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4-&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M207.5,-88.2C207.5,-98.41 207.5,-108.62 207.5,-118.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"207.5,-123.85 205.25,-118.85 207.5,-121.35 207.5,-118.85 207.5,-118.85 207.5,-118.85 207.5,-121.35 209.75,-118.85 207.5,-123.85 207.5,-123.85\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M207.5,-17.1C207.5,-33.3 207.5,-49.5 207.5,-65.7\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"207.5,-70.72 205.25,-65.72 207.5,-68.22 207.5,-65.72 207.5,-65.72 207.5,-65.72 207.5,-68.22 209.75,-65.72 207.5,-70.72 207.5,-70.72\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;5 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>5-&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M197.96,-17.19C192.7,-25.67 195.88,-35 207.5,-35 216.95,-35 220.81,-28.84 219.11,-21.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"217.04,-17.19 221.08,-20.88 218.03,-19.48 219.02,-21.78 219.02,-21.78 219.02,-21.78 218.03,-19.48 216.95,-22.67 217.04,-17.19 217.04,-17.19\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M89.33,-215C89.33,-215 67.67,-215 67.67,-215 64.83,-215 62,-212.17 62,-209.33 62,-209.33 62,-203.67 62,-203.67 62,-200.83 64.83,-198 67.67,-198 67.67,-198 89.33,-198 89.33,-198 92.17,-198 95,-200.83 95,-203.67 95,-203.67 95,-209.33 95,-209.33 95,-212.17 92.17,-215 89.33,-215\"/>\n",
       "<text text-anchor=\"start\" x=\"66\" y=\"-204\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,$</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M101.33,-141C101.33,-141 55.67,-141 55.67,-141 52.83,-141 50,-138.17 50,-135.33 50,-135.33 50,-129.67 50,-129.67 50,-126.83 52.83,-124 55.67,-124 55.67,-124 101.33,-124 101.33,-124 104.17,-124 107,-126.83 107,-129.67 107,-129.67 107,-135.33 107,-135.33 107,-138.17 104.17,-141 101.33,-141\"/>\n",
       "<text text-anchor=\"start\" x=\"54\" y=\"-130\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[#] $</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;8 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>6-&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.5,-197.82C78.5,-180.71 78.5,-163.6 78.5,-146.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.5,-141.17 80.75,-146.17 78.5,-143.67 78.5,-146.17 78.5,-146.17 78.5,-146.17 78.5,-143.67 76.25,-146.17 78.5,-141.17 78.5,-141.17\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M218.33,-237C218.33,-237 196.67,-237 196.67,-237 193.83,-237 191,-234.17 191,-231.33 191,-231.33 191,-225.67 191,-225.67 191,-222.83 193.83,-220 196.67,-220 196.67,-220 218.33,-220 218.33,-220 221.17,-220 224,-222.83 224,-225.67 224,-225.67 224,-231.33 224,-231.33 224,-234.17 221.17,-237 218.33,-237\"/>\n",
       "<text text-anchor=\"start\" x=\"195\" y=\"-226\" font-family=\"Courier,monospace\" font-size=\"10.00\">q3,$</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;9 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>6-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M95.07,-209.2C117.83,-213.14 160.22,-220.48 185.64,-224.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"190.8,-225.78 185.49,-227.14 188.34,-225.35 185.87,-224.93 185.87,-224.93 185.87,-224.93 188.34,-225.35 186.26,-222.71 190.8,-225.78 190.8,-225.78\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>7-&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.5,-250.85C78.5,-240.63 78.5,-230.42 78.5,-220.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.5,-215.2 80.75,-220.2 78.5,-217.7 78.5,-220.2 78.5,-220.2 78.5,-220.2 78.5,-217.7 76.25,-220.2 78.5,-215.2 78.5,-215.2\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.33,-88C107.33,-88 49.67,-88 49.67,-88 46.83,-88 44,-85.17 44,-82.33 44,-82.33 44,-76.67 44,-76.67 44,-73.83 46.83,-71 49.67,-71 49.67,-71 107.33,-71 107.33,-71 110.17,-71 113,-73.83 113,-76.67 113,-76.67 113,-82.33 113,-82.33 113,-85.17 110.17,-88 107.33,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"48\" y=\"-77\" font-family=\"Courier,monospace\" font-size=\"10.00\">q2,[#] # $</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;10 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>8-&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.5,-123.85C78.5,-113.63 78.5,-103.42 78.5,-93.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.5,-88.2 80.75,-93.2 78.5,-90.7 78.5,-93.2 78.5,-93.2 78.5,-93.2 78.5,-90.7 76.25,-93.2 78.5,-88.2 78.5,-88.2\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;11 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>8-&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.06,-132.5C126.7,-132.5 153.17,-132.5 173.87,-132.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"179,-132.5 174,-134.75 176.5,-132.5 174,-132.5 174,-132.5 174,-132.5 176.5,-132.5 174,-130.25 179,-132.5 179,-132.5\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;2 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9-&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M207.5,-219.89C207.5,-209.82 207.5,-199.75 207.5,-189.68\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"207.5,-184.41 209.75,-189.41 207.5,-186.91 207.5,-189.41 207.5,-189.41 207.5,-189.41 207.5,-186.91 205.25,-189.41 207.5,-184.41 207.5,-184.41\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;3 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>10-&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.5,-70.72C78.5,-54.52 78.5,-38.33 78.5,-22.13\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.5,-17.1 80.75,-22.1 78.5,-19.6 78.5,-22.1 78.5,-22.1 78.5,-22.1 78.5,-19.6 76.25,-22.1 78.5,-17.1 78.5,-17.1\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;4 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>10-&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M113.2,-79.5C129.85,-79.5 150.03,-79.5 167.36,-79.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"172.64,-79.5 167.64,-81.75 170.14,-79.5 167.64,-79.5 167.64,-79.5 167.64,-79.5 170.14,-79.5 167.64,-77.25 172.64,-79.5 172.64,-79.5\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;9 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>11-&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M178.76,-136.64C165.54,-140.14 151.04,-146.59 143,-158.5 127.14,-182 161.5,-205.44 185.9,-218.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"190.63,-220.78 185.15,-220.49 188.41,-219.64 186.19,-218.49 186.19,-218.49 186.19,-218.49 188.41,-219.64 187.22,-216.49 190.63,-220.78 190.63,-220.78\"/>\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": [
    "The graph shows us the first few pushes, but after the stack gets deep enough, only the top few items are shown, and the pushes stop creating new nodes. What isn't apparent from the run graph is that the simulator does make sure that the same number of `#` signs are pushed and popped."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
