{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 6: CFGs and PDAs are equivalent" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import matplotlib.patches as patches, matplotlib.lines as lines" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Monday reading\n", "\n", "Read Section 2.2, Lemma 2.21." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tuesday class\n", "\n", "This week we'll show that the two models we learned last week, context-free grammars and pushdown automata, are equivalent. Today we will show how to convert a context-free grammar to a pushdown automaton, which is important because it is the basis for a lot of _parsing_ algorithms (algorithms that take a string as input, decide whether it belongs to the language, and if so, generates a tree as output).\n", "\n", "### The top-down construction\n", "\n", "The construction used in the proof of Lemma 2.21 is known as _top-down_ or sometimes \"nondeterministic LL\" parsing.\n", "\n", "The basic idea is pretty simple, and probably easier to describe first without getting into the details of the PDA. The stack is initialized to $S\\mathtt{$}$ (remember that the top of the stack is on the left). \n", "\n", "Whenever the top stack symbol is a terminal symbol and it matches the next input symbol, we pop it and read in the input symbol. If it doesn't match, then this path of the derivation rejects.\n", "\n", "Whenever the top stack symbol is a nonterminal symbol, we pop it and nondeterministically push _all possible_ replacements for the nonterminal. Each replacement is pushed in reverse order, so that the leftmost symbol is on the top.\n", "\n", "If we reach the end of the input string and the stack just has $\\mathtt{$}$, then we accept.\n", "\n", "Here's an example grammar:\n", "\n", "\\begin{align*}\n", "S &\\rightarrow \\mathtt{a} T \\mathtt{b} \\\\\n", "S &\\rightarrow \\mathtt{b} \\\\\n", "T &\\rightarrow T \\mathtt{a} \\\\\n", "T &\\rightarrow \\varepsilon\n", "\\end{align*}\n", "\n", "Here's what the _successful_ parse looks like for string `aaab`:\n", "\n", "| Input | Stack |\n", "|-------|-------|\n", "|`aaab` | _S_`$`|\n", "|`aaab` | `a`_T_`b$` |\n", "|`aab` | _T_`b$` |\n", "|`aab` | _T_`ab$` |\n", "|`aab` | _T_`aab$` |\n", "|`aab` | `aab$` |\n", "|`ab` | `ab$` |\n", "|`b` | `b$` |\n", "|$\\varepsilon$ | `$` |\n", "\n", "There are also many unsuccessful parses, but as long as one of them succeeds, we accept the string." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The conversion from CFG to PDA basically implements the above algorithm in the PDA. This construction is implemented in Tock:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "0\n", "\n", "start\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "0.1\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "2\n", "\n", "loop\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "ε,ε → S\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "ε,S → b\n", "ε,T → ε\n", "a,a → ε\n", "b,b → ε\n", "\n", "\n", "\n", "3\n", "\n", "1.2\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "ε,S → b\n", "\n", "\n", "\n", "5\n", "\n", "3.1\n", "\n", "\n", "\n", "2->5\n", "\n", "\n", "ε,T → a\n", "\n", "\n", "\n", "6\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "2->6\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "4\n", "\n", "1.1\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε,ε → T\n", "\n", "\n", "\n", "4->2\n", "\n", "\n", "ε,ε → a\n", "\n", "\n", "\n", "5->2\n", "\n", "\n", "ε,ε → T\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "g = Grammar.from_lines([\"S -> a T b\",\n", " \"S -> b\",\n", " \"T -> T a\",\n", " \"T -> &\"])\n", "p1 = from_grammar(g)\n", "to_graph(p1)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "5\n", "\n", "start,ε\n", "\n", "\n", "\n", "_START->5\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "\n", "\n", "1\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "2\n", "\n", "\n", "\n", "1->2\n", "\n", "\n", "a\n", "\n", "\n", "\n", "3\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "b\n", "\n", "\n", "\n", "6\n", "\n", "0.1,$\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "loop,[S] $\n", "\n", "\n", "\n", "6->7\n", "\n", "\n", "\n", "\n", "\n", "8\n", "\n", "1.2,[b] $\n", "\n", "\n", "\n", "7->8\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "7->9\n", "\n", "\n", "\n", "\n", "\n", "10\n", "\n", "1.1,[T] b $\n", "\n", "\n", "\n", "8->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "loop,[a] T b …\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "loop,[T] b $\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "13\n", "\n", "3.1,[a] b $\n", "\n", "\n", "\n", "12->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "12->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "\n", "loop,[T] a b …\n", "\n", "\n", "\n", "13->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "\n", "3.1,[a] a b …\n", "\n", "\n", "\n", "15->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "\n", "loop,[a] b $\n", "\n", "\n", "\n", "15->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "\n", "loop,[T] a a …\n", "\n", "\n", "\n", "16->18\n", "\n", "\n", "\n", "\n", "\n", "19\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "17->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "\n", "3.1,[a] a a …\n", "\n", "\n", "\n", "18->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "\n", "loop,[a] a b …\n", "\n", "\n", "\n", "18->21\n", "\n", "\n", "\n", "\n", "\n", "23\n", "\n", "loop,[a] a a …\n", "\n", "\n", "\n", "18->23\n", "\n", "\n", "\n", "\n", "\n", "20->18\n", "\n", "\n", "\n", "\n", "\n", "20->23\n", "\n", "\n", "\n", "\n", "\n", "22\n", "\n", "loop,[a] b $\n", "\n", "\n", "\n", "21->22\n", "\n", "\n", "\n", "\n", "\n", "24\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "22->24\n", "\n", "\n", "\n", "\n", "\n", "26\n", "\n", "loop,[a] a b …\n", "\n", "\n", "\n", "23->26\n", "\n", "\n", "\n", "\n", "\n", "28\n", "\n", "loop,[a] a a …\n", "\n", "\n", "\n", "23->28\n", "\n", "\n", "\n", "\n", "\n", "25\n", "\n", "loop,$\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n", "27\n", "\n", "\n", "accept,ε\n", "\n", "\n", "\n", "25->27\n", "\n", "\n", "\n", "\n", "\n", "29\n", "\n", "loop,[a] b $\n", "\n", "\n", "\n", "26->29\n", "\n", "\n", "\n", "\n", "\n", "30\n", "\n", "loop,[a] a a …\n", "\n", "\n", "\n", "28->30\n", "\n", "\n", "\n", "\n", "\n", "31\n", "\n", "loop,[a] a b …\n", "\n", "\n", "\n", "28->31\n", "\n", "\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "run(p1, \"a a a b\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Convert the following CFG to a PDA:\n", "\n", "\\begin{align*}\n", "S &\\rightarrow \\mathtt{0} S \\mathtt{0} \\\\\n", "S &\\rightarrow \\mathtt{1} S \\mathtt{1} \\\\\n", "S &\\rightarrow \\varepsilon\n", "\\end{align*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** If you actually had to implement a parser this way, how would you do it? What would its time complexity be?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The bottom-up construction (optional)\n", "\n", "There's another parsing strategy that the book doesn't mention at this point. It's called _bottom-up_, _shift-reduce_, or maybe sometimes \"nondeterministic LR\" parsing. It's the basis for most parsing algorithms that are used in compilers.\n", "\n", "The idea is again pretty simple -- it's like top-down parsing in reverse. The stack is initialized to $\\mathtt{\\$}$. At any point in time, we can do two operations.\n", "\n", "In a _shift_, we read in one input symbol and push it onto the stack.\n", "\n", "In a _reduce_, we check to see if the prefix (top symbols) of the stack match a right-hand-side of a rule (in reverse order), and if so, we can pop those symbols and replace them with the left-hand-side of the rule.\n", "\n", "This algorithm is again nondeterministic: it's always possible to do a shift unless we're at the end of the string, and it may be possible to do several different reduces.\n", "\n", "If we reach the end of the input and the stack has just $S\\mathtt{\\$}$, then we accept.\n", "\n", "Here's what the _successful_ parse looks like for string `aaab`:\n", "\n", "| Input | Stack |\n", "|-------|-------|\n", "|`aaab` | `$`|\n", "|`aab` | `a$` |\n", "|`aab` | _T_`a$` |\n", "|`ab` | `a`_T_`a$` |\n", "|`ab` | _T_`a$` |\n", "|`b` | `a`_T_`a$` |\n", "|`b` | _T_`a$` |\n", "|$\\varepsilon$ | `b`_T_`a$` |\n", "|$\\varepsilon$ | _S_`$` |\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "3\n", "\n", "start\n", "\n", "\n", "\n", "_START->3\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "1\n", "\n", "0.1\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "2\n", "\n", "3.1\n", "\n", "\n", "\n", "4\n", "\n", "loop\n", "\n", "\n", "\n", "2->4\n", "\n", "\n", "ε,T → T\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "4->1\n", "\n", "\n", "ε,S → ε\n", "\n", "\n", "\n", "4->2\n", "\n", "\n", "ε,a → ε\n", "\n", "\n", "\n", "4->4\n", "\n", "\n", "ε,b → S\n", "ε,ε → T\n", "a,ε → a\n", "b,ε → b\n", "\n", "\n", "\n", "5\n", "\n", "1.2\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "ε,b → ε\n", "\n", "\n", "\n", "6\n", "\n", "1.1\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "ε,T → ε\n", "\n", "\n", "\n", "6->4\n", "\n", "\n", "ε,a → S\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "p2 = from_grammar(g, mode=\"bottomup\")\n", "to_graph(p2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Wednesday reading\n", "\n", "Read Section 2.2, Lemma 2.27." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Thursday class\n", "\n", "The conversion from a PDA to a CFG is probably the trickiest to understand of all the constructions we do in this class. Fortunately, though, it's not very difficult to perform." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example\n", "\n", "Let's start with an example PDA, one that recognizes the language of balanced parentheses but using `a` and `b` for left and right parentheses:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "2\n", "\n", "q1\n", "\n", "\n", "\n", "_START->2\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q2\n", "\n", "\n", "\n", "0->0\n", "\n", "\n", "a,ε → #\n", "b,# → ε\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q3\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "2->0\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "mc = read_csv(\"pda-parens.csv\")\n", "to_graph(mc)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "27\n", "\n", "q1,ε\n", "\n", "\n", "\n", "_START->27\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "13\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "0->13\n", "\n", "\n", "\n", "\n", "\n", "1\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "3\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "\n", "\n", "\n", "4\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "\n", "\n", "\n", "5\n", "\n", "q2,$\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "\n", "q3,ε\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "9\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "7->9\n", "\n", "\n", "\n", "\n", "\n", "8\n", "\n", "q3,ε\n", "\n", "\n", "\n", "10\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "11\n", "\n", "q2,[#] # # # $\n", "\n", "\n", "\n", "10->11\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "12->1\n", "\n", "\n", "\n", "\n", "\n", "13->2\n", "\n", "\n", "\n", "\n", "\n", "14\n", "\n", "\n", "\n", "16\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "a\n", "\n", "\n", "\n", "15\n", "\n", "\n", "\n", "18\n", "\n", "\n", "\n", "15->18\n", "\n", "\n", "a\n", "\n", "\n", "\n", "17\n", "\n", "\n", "\n", "16->17\n", "\n", "\n", "a\n", "\n", "\n", "\n", "17->15\n", "\n", "\n", "a\n", "\n", "\n", "\n", "19\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "b\n", "\n", "\n", "\n", "20\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "b\n", "\n", "\n", "\n", "22\n", "\n", "\n", "\n", "20->22\n", "\n", "\n", "b\n", "\n", "\n", "\n", "21\n", "\n", "\n", "\n", "23\n", "\n", "\n", "\n", "21->23\n", "\n", "\n", "a\n", "\n", "\n", "\n", "22->21\n", "\n", "\n", "a\n", "\n", "\n", "\n", "24\n", "\n", "\n", "\n", "23->24\n", "\n", "\n", "b\n", "\n", "\n", "\n", "25\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "b\n", "\n", "\n", "\n", "26\n", "\n", "\n", "\n", "25->26\n", "\n", "\n", "b\n", "\n", "\n", "\n", "28\n", "\n", "q2,$\n", "\n", "\n", "\n", "27->28\n", "\n", "\n", "\n", "\n", "\n", "28->7\n", "\n", "\n", "\n", "\n", "\n", "28->8\n", "\n", "\n", "\n", "\n", "" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "w = list(\"aaaabbbaabbb\")\n", "r = run(mc, w, show_stack=100)\n", "r" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The book uses plots of stack height over time (Figure 2.28 and 2.29) to help illustrate the construction. Here's a function that produces similar plots (you don't need to understand this):" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def plot_height(ax, path):\n", " n = len(path)\n", " heights = [len(c[2]) for c in path]\n", " bars = ax.bar(np.arange(n), heights)\n", " ax.set_xticks(np.arange(n-1)+0.5)\n", " labels = []\n", " for i in range(n-1):\n", " if len(path[i][1]) > len(path[i+1][1]):\n", " labels.append(path[i][1][0])\n", " else:\n", " labels.append(\"\")\n", " ax.set_xticklabels(labels)\n", " ax.set_xlabel(\"input string\")\n", " ax.set_yticks(np.arange(max(heights)+1))\n", " ax.set_ylim(ymax=max(heights)+0.5)\n", " ax.set_ylabel(\"stack height\")\n", " \n", " for c, b in zip(path, bars):\n", " h = b.get_height()\n", " ax.text(b.get_x() + b.get_width()/2., h, c[0], ha=\"center\", va=\"bottom\")\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAXwUlEQVR4nO3df3Dkd33f8efb6MAn7MN1rLQQ9MNMOGuACnlXhfPYUh1AlORcJTulXWIlbTO0V6aVY0KlzlGFQYVuz0raNEnPQTkGNVJjo6mF1UhyIpOq9qBrAftknVWBsX1Djpg4ibkWYdlRVMu8+8d+ddYp+rGS9ru7349ej5kd7e73u5/vi++Xfd3X+/3ud83dERGR8FxV7gAiIhIPFbyISKBU8CIigVLBi4gESgUvIhKoqnIHWO+GG27whoaGcscQEUmM2dnZS+5es9m0iir4hoYGzp07V+4YIiKJYWbf2WqaPqIREQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl7Krqenh8bGRpqamshkMiwuLpY7kkgQVPBSdu3t7SwsLDA/P8/Ro0c5depUuSOJBKGirkUj4cvlcgwPD1NbW0tNTQ3pdJru7u7L048dO8bo6GgZE4qEQwUvJTM7O8vIyAhzc3Osrq6SSqVIp9NXzDM4OEg2my1TQpGwqOClZGZmZshkMlRXVwPQ0dFxxfRcLkdVVRWdnZ3liCcSHBW8lJSZbfr80NAQk5OTTE9PbzmPiOxOrAdZzeyimf1vMztvZrrQ+wHX1tbG2NgYy8vLLC0tMTExAcDU1BT9/f2Mj49f3rsXkf0rxR78T7j7pRIsRypcKpUim83S3NxMfX09ra2tAHR1dbGyskJ7ezuQP9A6MDBQzqgiQdBHNFJSvb299Pb2AtDX1wfAhQsXyphIJFxxF7wDXzYzB37b3c9snMHMTgAnAOrq6mKOI+XQcPKhTZ9fPPsMdugwpy9tPn3NxXuOxxFLJHhxF/yt7v68mf0o8Idm9i13/8r6GaLSPwPQ0tLiMeeRCnLdbTpbRiROsR5kdffno78vAGPAe+JcnoiIvCa2gjezN5rZtWv3gQ8CC3EtT0RErhTnRzR/HRiLzmmuAu5396kYlyciIuvEVvDu/m3g3XGNLyIi29PVJEVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCl13p6emhsbGRpqYmMpkMi4uL5Y60qaTkrHRaj8mmgpddaW9vZ2Fhgfn5eY4ePcqpU6fKHWlTSclZ6bQek62q3AGkcuVyOYaHh6mtraWmpoZ0Ok13d/fl6ceOHWN0dLSMCfOSkrPSaT2GRwUvm5qdnWVkZIS5uTlWV1dJpVKk0+kr5hkcHCSbzZYpYV5SclY6rccwqeBlUzMzM2QyGaqrqwHo6Oi4Ynoul6OqqorOzs5yxLssKTkrndZjmFTwsiUz2/T5oaEhJicnmZ6e3nKeUkpKzkqn9Rie2A+ymtnrzGzOzCbjXpYUT1tbG2NjYywvL7O0tMTExAQAU1NT9Pf3Mz4+fnlvr5ySkrPSaT2GqRR78HcDTwFHSrAsKZJUKkU2m6W5uZn6+npaW1sB6OrqYmVlhfb2diB/4G1gYEA5E07rMUzm7vENbvZWYAjIAZ9w9zu2m7+lpcXPnTsXWx7Zu76+Pq655porzqooVMPJh/a17Iv3HC943v3klNdoPSaHmc26e8tm0+Leg/914F8B1241g5mdAE4A1NXVxRxHdrJVGS+efQY7dJjTl3Yu690U8l5s9w9GoTnjzpgEWo/hi63gzewO4AV3nzWz27eaz93PAGcgvwcfVx7Zn+tuS8bZE0nJWem0HsMQ50HWW4EOM7sIjADvM7PfjXF5IiKyTmwF7+6fdPe3unsD8BHgf7j7z8W1PBERuZKuRSMiEqiSfNHJ3R8FHi3FskREJE978CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gEaseCN7O/X8hzIiJSWQrZg/9kgc+JiEgF2fIHP8zsJ4GfAn7MzH5z3aQjwGrcwUREZH+2+0Wn54FzQAcwu+75JeCX4gwlIiL7t2XBu/uTwJNmdr+7v1LCTCIiUgSF/Cbre8ysD6iP5jfA3f1tcQYTEZH9KaTgv0D+I5lZ4NV444iISLEUUvA/cPc/iD2JiIgU1XZn0aSiu4+Y2a8CDwIra9Pd/YmYs4mIyD5stwf/HzY8bll334H3FT+OiIgUy5ZfdHL3n9jmpnJPiJ6eHhobG2lqaiKTybC4uFjuSImUhPWojLJRIZcq+MQmt4+aWXMpAsr+tLe3s7CwwPz8PEePHuXUqVPljpRISViPyigbFXKQtSW6TUSPjwOPAx8zswfc/VfiCie7k8vlGB4epra2lpqaGtLpNN3d3ZenHzt2jNHR0TImTIYkrEdllEIUUvA/AqTc/SUAM/s0MAq0kT91UgVfAWZnZxkZGWFubo7V1VVSqRTpdPqKeQYHB8lms2VKmAxJWI/KKIUqpODrgP+37vErQL27L5vZyhavkRKbmZkhk8lQXV0NQEdHxxXTc7kcVVVVdHZ2liNeYiRhPSqjFKqQgr8f+JqZ/V70+O8CXzSzNwLfjC2Z7JqZbfr80NAQk5OTTE9PbzmPvCYJ61EZpRA7HmR1988C/xRYBH4AfMzdP+PuL7v7lv/8mtnVZvaYmT1pZt8ws39TvNiyUVtbG2NjYywvL7O0tMTERP6QydTUFP39/YyPj1/em5KtJWE9KqMUarsvOh1x9xfN7Hrgj6Lb2rTr3f3/7jD2CvA+d3/JzA4BZ83sD9z9a0VJLldIpVJks1mam5upr6+ntbUVgK6uLlZWVmhvbwfyB7YGBgbKGbWiJWE9KqMUaruPaO4H7iB/INWJLjK27u+2Fxtzdwdeih4eim6+z7yyjd7eXnp7ewHo6+sD4MKFC2VMlExJWI/KKIXY7nLBd0R/b9zr4Gb2OvL/QPw4cK+7f32TeU4AJwDq6ur2uqgDqeHkQ1tOWzz7DHboMKcvbT0PwMV7jhc7ViJttS4raT0qo+zWjgdZLX8UpBO40d0/a2Z1wN9w98d2eq27vwo0m9l1wJiZvcvdFzbMcwY4A9DS0qI9/CK57jadnVAMSViPyihbKeQ3WX8LuAW4M3q8BNy7m4W4+yLwKPCh3bxORET2rpCCf6+7/wvgLwHc/fvA63d6kZnVRHvumNlh4APAt/aRVUREdqGQ8+BfiT5Ld8gXN/DDAl73ZmAoeu1VwH9198k9JxURkV0ppOB/ExgDftTMcsCHgV/e6UXuPg/cvL94IiKyVzsWvLvfZ2azwPvJnyL5M+7+VOzJRERkXwrZgwd4FnhxbX4zq3P3P44tlYiI7Fshp0neBXwa+HPyP7q99kWnpnijiYjIfhSyB383cJO7/5+4w4iISPEUcprkc+QvMiYiIgmy3cXGPhHd/TbwqJk9RP4CYgC4+6/FnE1ERPZhu49oro3+/nF0ez0FfMFJREQqw3YXG9P120VEEqyQz+BFRCSBVPAiIoHaseCjX3Ta+NyerxEvIiKlUcge/ISZHVl7YGbvACbiiyQiIsVQSMH/O/Ilf42ZpYEHgJ+LN5aIiOxXIRcbeyj60ewvkz918mfc/dnYk4mIyL5s90Wn/8SVP5J9hPyXnu4yM9z9F+MOJyIie7fdHvy5DY9n4wwiIiLFtd0XnYYAzOyNwF9GP6BN9AtNbyhNPBER2atCDrJOA4fXPT4M/Pd44oiISLEUUvBXu/tLaw+i+9XxRRIRkWIopOBfNrPU2oPoVMnl+CKJiEgxFPKDHx8HHjCz56PHbway8UUSEZFiKOQ8+MfNrBG4ifzP9X3L3V+JPZmIiOxLoT+6fRPwDuBq4OboPPjh+GKJiMh+FfKj258Gbidf8L8P/CRwFlDBi4hUsEIOsn4YeD/wZ+7+C8C70XnwIiIVr5CCX3b3HwKr0VUlXwDeFm+sg6mnp4fGxkaamprIZDIsLi6WO5LESNu7OLQet1ZIwZ8zs+uAz5O/XMETwGOxpjqg2tvbWVhYYH5+nqNHj3Lq1KlyR5IYaXsXh9bj1go5i+afR3cHzGwKOOLu8/HGCl8ul2N4eJja2lpqampIp9N0d3dfnn7s2DFGR0fLmFCKSdu7OLQed6eQg6zT7v5+AHe/uPE52b3Z2VlGRkaYm5tjdXWVVCpFOp2+Yp7BwUGyWX3dIATa3sWh9bh7210u+GrylyS4wcz+Gvlz4CF/2eC3lCBbsGZmZshkMlRX56/40NHRccX0XC5HVVUVnZ2d5YgnRabtXRxaj7u33R78PyP/Lda3kP/sfa3gXwTujTlX8Mxs0+eHhoaYnJxkenp6y3kkebS9i0PrcXe2PMjq7r/h7jcC3e7+Nne/Mbq9291P7zSwmdWa2SNm9pSZfcPM7i5q8gRra2tjbGyM5eVllpaWmJjI/8Tt1NQU/f39jI+PX95LkeTT9i4OrcfdK+SbrH9mZte6+5KZ/TKQAv6tuz+xw+tWgX/p7k+Y2bXArJn9obt/c7+hky6VSpHNZmlubqa+vp7W1lYAurq6WFlZob29HcgfMBoYGChnVCkCbe/i0HrcvUIK/lPu/oCZ3Qb8HeDfA58D3rvdi9z9T4E/je4vmdlTwI8BB77gAXp7e+nt7QWgr68PgAsXLpQxkcRJ27s4tB53p5CCfzX6exz4nLv/npn17WYhZtYA3Ax8fZNpJ4ATAHV1dbsZNnEaTj606fOLZ5/BDh3m9KXNp6+5eM/xOGJJDLba1qDtvVt63+xdIQX/J2b228AHgH4zewOFfUEKADO7BvgS8HF3f3HjdHc/A5wBaGlp8Y3TD4LrbtNR/4NE27s4tB53VkhR/wPgYeBD7r4IXA/0FDK4mR0iX+73ufuDe04pIiK7Vsg3Wf8CeHDd48ufrW/H8ucqfQF4yt1/bT8hRURk9wr+qGUPbgV+HnifmZ2Pbj8V4/JERGSdQn/wY9fc/SyvfTlKRERKLM49eBERKSMVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBb8PPT09NDY20tTURCaTYXFxsdyRRGSfQnpfq+D3ob29nYWFBebn5zl69CinTp0qdyQR2aeQ3tdV5Q6QFLlcjuHhYWpra6mpqSGdTtPd3X15+rFjxxgdHS1jQhHZrdDf1yr4AszOzjIyMsLc3Byrq6ukUinS6fQV8wwODpLNZsuUUER26yC8r1XwBZiZmSGTyVBdXQ1AR0fHFdNzuRxVVVV0dnaWI56I7MFBeF+r4AtkZps+PzQ0xOTkJNPT01vOIyKVKfT3dWwHWc1s0MxeMLOFuJZRKm1tbYyNjbG8vMzS0hITExMATE1N0d/fz/j4+OW9ABFJhoPwvo5zD/53gNPAcIzLKIlUKkU2m6W5uZn6+npaW1sB6OrqYmVlhfb2diB/QGZgYKCcUUWkQAfhfR1bwbv7V8ysIa7xS623t5fe3l4A+vr6ALhw4UIZE4nIfoX+vi77Z/BmdgI4AVBXV1fmNK9pOPnQltMWzz6DHTrM6UtbzwNw8Z7jxY4lIvu01Xu70Pc1JOe9XfaCd/czwBmAlpYWL3Ocglx3W3KPqovI5kJ8X+ubrCIigVLBi4gEKs7TJL8IfBW4ycy+a2YfjWtZIiLyV8V5Fs3PxjW2iIjsTB/RiIgESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gE6sAU/AMPPMA73/lOrrrqKs6dO1fuOCJygHzqU5+iqamJ5uZmPvjBD/L888+XZLkHpuDf9a538eCDD9LW1lbuKCJywPT09DA/P8/58+e54447+MxnPlOS5VaVZCkllsvlGB4epra2lpqaGtLpNN3d3eWOJSIHwE798/LLL2NmJckSXMHPzs4yMjLC3Nwcq6urpFIp0ul0uWOJyAGwXf/09vYyPDzMm970Jh555JGS5AnuI5qZmRkymQzV1dUcOXKEjo6OckcSkQNiu/7J5XI899xzdHZ2cvr06ZLkCa7ggZL954+IyEY79c+dd97Jl770pZJkibXgzexDZva0mV0ws5NxLmtNW1sbY2NjLC8vs7S0xMTERCkWKyKyZf88++yzl+cZHx+nsbGxJHli+wzezF4H3Au0A98FHjezcXf/ZlzLBEilUmSzWZqbm6mvr6e1tRWAsbEx7rrrLr73ve9x/Phxmpubefjhh+OMIiIHzFb9c/LkSZ5++mmuuuoq6uvrGRgYKEmeOA+yvge44O7fBjCzEeCngVgLHvIHM3p7ewHo6+sDIJPJkMlk4l60iBxwm/VPqT6S2cjcPZ6BzT4MfMjd/0n0+OeB97p714b5TgAnooc3AU8XOcpbgFeBPy9w/huAS0XOUOwxk5AxjjGVsTLHS8qY5ci42/7Zi3p3r9lsQpx78Jsdafgr/5q4+xngTIw5dsXMzrl7SyWPmYSMcYypjJU5XlLGTELGYovzIOt3gdp1j98KlOb7uSIiEmvBPw683cxuNLPXAx8BxmNcnoiIrBPbRzTuvmpmXcDDwOuAQXf/RlzLK6I4Pi4q9phJyBjHmMpYmeMlZcwkZCyq2A6yiohIeQX5TVYREVHBi4gESwUvFc/MGsxsoVLHi2vMJNC2qWwqeBGRQKngY2Rm/83MZs3sG9E3dg/EmHFkBKrMbMjM5s1s1MyqK2y8oo+ZhG0dOXDbJjHcXbeYbsD10d/DwALwIwdhzBjGayD/Lehbo8eDQHeljBfjmEnY1gdy2yTlpj34eP2imT0JfI38t3rffkDGjCPjc+7+P6P7vwvcVmHjxTFmErY1HMxtkwjB/WRfpTCz24EPALe4+1+Y2aPA1aGPGUfGyMYvbOz3CxzFHq+oYyZhW69zoLZNkmgPPj5vAr4fvZEagWMHZMw4MgLUmdkt0f2fBc5W2HjFHjMJ23rNQds2iaGCj88U+QM788Bnyf8n8UEYM46MAE8B/yga93rgcxU2XrHHTMK2XnPQtk1i6FIFIiKB0h68iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPCSSGb2v2IYs8HM7tzla/71DtN/38yu218ykb3RaZIikeibnt3ufscuXvOSu1+zyfNG/v31wyJGFNkV7cFLIpnZS9Hf283s0egKgd8ys/uicsXMLppZv5k9Ft1+PHr+d8zswxvHAu4BWs3svJn90oblvdnMvhJNWzCzVjO7BzgcPXdf9F8AT5nZbwFPALVRhhvWTft8dCXHL5vZ4WjsvxVd5fCrZvardkCvXS7Fp4KXENwMfBx4B/A24NZ101509/cAp4Ff32Gck8CMuze7+3/cMO1O4GF3bwbeDZx395PAcjR/ZzTfTcCwu9/s7t/ZMMbbgXvd/Z3AIvD3ouf/M/Axd78FeLXA/80iO1LBSwgec/fvRh+HnCd/edg1X1z395aNL9yFx4FfMLM+4G+6+9IW833H3be6BMAfufv56P4s0BB9Pn+tu68dU7h/HxlFrqCClxCsrLv/KldeJdU3ub9K9P/96OOc1++0AHf/CtAG/AnwX8zsH24x68u7zGk7LVtkr1TwErrsur9fje5fBNLR/Z8GDkX3l4BrNxvEzOqBF9z988AXgFQ06RUzO7TZawrh7t8Hlsxs7cqOH9nrWCIbqeAldG8ws68DdwNrB04/D/xtM3sMeC+v7XXPA6tm9uTGg6zA7cB5M5sj/9n5b0TPnwHmzey+fWT8KHDGzL5Kfo/+B/sYS+QynSYpwTKzi0CLu18qd5btmNk17r52VtBJ4M3ufneZY0kA9ItOIuV33Mw+Sf79+B3gH5c3joRCe/AiIoHSZ/AiIoFSwYuIBEoFLyISKBW8iEigVPAiIoH6/8m/hEWSTmQ8AAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each bar (including bars with zero height) represents a configuration of the machine as it reads the string. The machine's state is written above the bar. The horizontal axis shows the input symbols that are read in (if any) and the vertical axis is the height of the stack. In this case, notice how the stack grows whenever an `a` is read and shrinks whenever a `b` is read.\n", "\n", "You can try changing the input string `w` or even the PDA to see how the above graph changes. (However, the figures below will get messed up.)\n", "\n", "A sequence of configurations like this is called a _run_. Let's define a _sub-run_ to be a contiguous subsequence of a run that begins and ends with the same stack $t$ and does not pop any symbols in $t$ (not even if it pushes the same symbols back).\n", "\n", "For example, the blue rectangle below highlights a sub-run:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAZdUlEQVR4nO3df3xU9Z3v8ddHEgtUAX9gLUoS7YoKJcQkt8IDAS1QpbKwPNCbrtl210dd9MHVle2FW2u2D9Gaa/1x97LesEIodMkughdKWKDLL5G06ApC5MdFrT8eXbt22a313lIBESH93D9mgkmaHxMyZ87MN+/n4zGPzMw58z3vntN5czxn5oy5OyIiEp5z4g4gIiLRUMGLiARKBS8iEigVvIhIoFTwIiKByos7QEsXX3yxFxUVxR0jNh9+fCruCCI5Z0Df/LgjxKqxsfEDdx/c3rSsKviioiL27t0bd4zYPP/6r+KOIJJzJg3/XNwRYmVmv+homg7RiIgESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gEKqu+ySq9U+1TD7OrYRt5+fkMGVrE3EcXcN6AgXHHEsl52oOX2JWOmcCSdQ3U1u/gssIrWbnk6bgjiQRBe/CSUSsWL+D59asZfOkQBl5wEcNGFHP7nbPPTL92VBk7t26MMaFIOFTwkjFvvXaAhk3reGbNNpqamph922SGjShuNc+WtSuZMGV6TAlFwqKCl4w51LibsROn0LdffwDG3HRzq+krFi+gT14eE6fOjCOeSHBU8JJRZtbu81vXPcfun2zjiaWrO5xHRLon0pOsZvaumf0fM9tvZr33Qu8CwMjy0by0fRMnPz7BR8eP8XLDVgD27HyB55bW8EjN8jN79yLSc5nYg7/J3T/IwHIky101vJgJt0znnpmTuGTI5Ywsux6AmuoHOXXqE759VwWQONE656En4owqEgQdopGMqrx7DpV3zwGgbuGTACzfvCvOSCLBirrgHdhqZg4sdvfatjOY2SxgFkBBQUHEcSQOd9W1f3TuyIHDWH4/tvTp/OjdD75RHkUskeBFXfBj3f2wmV0CbDOzn7n7T1vOkCz9WoDy8nKPOI9kkUE3VMYdQSRokZ5kdffDyb/vA/XAl6JcnoiIfCqygjezz5rZ+c33ga8Ah6JanoiItBblIZrPAfXJzzTnAc+6++YIlyciIi1EVvDu/nNgVFTji4hI53Q1SRGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQOXFHUByS+1TD7OrYRt5+fkMGVrE3EcXcN6AgXHH+j25kjPbaT3mNu3BS7eUjpnAknUN1Nbv4LLCK1m55Om4I7UrV3JmO63H3KY9eOnQisULeH79agZfOoSBF1zEsBHF3H7n7DPTrx1Vxs6tG2NMmJArObOd1mN4VPDSrrdeO0DDpnU8s2YbTU1NzL5tMsNGFLeaZ8valUyYMj2mhAm5kjPbaT2GSQUv7TrUuJuxE6fQt19/AMbcdHOr6SsWL6BPXh4Tp86MI94ZuZIz22k9hkkFLx0ys3af37ruOXb/ZBtPLF3d4TyZlCs5s53WY3giP8lqZn3MbJ+Z6eBdDhlZPpqXtm/i5Mcn+Oj4MV5u2ArAnp0v8NzSGh6pWX5mby9OuZIz22k9hikTe/D3A28AAzKwLEmTq4YXM+GW6dwzcxKXDLmckWXXA1BT/SCnTn3Ct++qABIn3uY89IRy5jitxzCZu0c3uNnlwHKgGviWu0/tbP7y8nLfu3dvZHmy3fOv/yruCB2qW/gk/fp/ttWnKlJ1V13PtukPvlGe8rw9ySmfyqX1OGn45+KOECsza3T3dt8kUe/BLwD+G3B+RzOY2SxgFkBBQUHEcaQrHZXxkQOHsfx+bOnTdVl3p5DPRmf/YKSaM+qMuUDrMXyRFbyZTQXed/dGM7uxo/ncvRaohcQefFR5pGcG3VAZd4SU5ErObKf1GIYoT7KOBaaZ2bvAKuDLZvYPES5PRERaiKzg3f077n65uxcBXwNecPc/iWp5IiLSmq5FIyISqIx80cndG4CGTCxLREQStAcvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKC6LHgzuz2V50REJLuksgf/nRSfExGRLNLhD36Y2RTgq8BlZvZ0i0kDgNNRBxMRkZ7p7BedDgN7gWlAY4vnjwJ/GWUoERHpuQ4L3t0PAAfM7Fl3P5XBTCIikgap/Cbrl8xsPlCYnN8Ad/crowwmIiI9k0rBLyVxSKYRaIo2joiIpEsqBf9bd98UeRIREUmrzj5FU5q8u8PMngTWAiebp7v7qxFnExGRHuhsD/5/tHlc3uK+A19OfxwREUmXzj5Fc1Mmg0g0ap96mF0N28jLz2fI0CLmPrqA8wYMjDtWzsmF9aiM0lYqlyr4Vju3b5pZSSYCSs+UjpnAknUN1Nbv4LLCK1m55OmuXyS/JxfWozJKW6mcZC1P3jYkH98K7AHuMbPV7v5EVOGke1YsXsDz61cz+NIhDLzgIoaNKOb2O2efmX7tqDJ2bt0YY8LckAvrURklFakU/EVAqbsfAzCzh4A1wHgSH51UwWeBt147QMOmdTyzZhtNTU3Mvm0yw0YUt5pny9qVTJgyPaaEuSEX1qMySqpSKfgC4JMWj08Bhe5+wsxOdvAaybBDjbsZO3EKffv1B2DMTTe3mr5i8QL65OUxcerMOOLljFxYj8ooqUql4J8FdpnZPyYf/yGw0sw+C7weWTLpNjNr9/mt655j90+28cTS1R3OI5/KhfWojJKKLk+yuvv3gD8HjgC/Be5x90fc/bi7V3b0OjPra2avmNkBM3vNzB5OX2xpa2T5aF7avomTH5/go+PHeLlhKwB7dr7Ac0treKRm+Zm9KelYLqxHZZRUdfZFpwHu/qGZXQj8S/LWPO1Cd/9/XYx9Eviyux8zs3zgRTPb5O670pJcWrlqeDETbpnOPTMnccmQyxlZdj0ANdUPcurUJ3z7rgogcWJrzkM6bdKRXFiPyiip6uwQzbPAVBInUp3kRcZa/O30YmPu7sCx5MP85M17mFc6UXn3HCrvngNA3cInAVi+Wf+edlcurEdllFR09kWnqcm/V5zt4GbWh8Q/EH8ALHT33e3MMwuYBVBQUHC2i+qV7qrb2+G0IwcOY/n92NKn43kAfvCN8k6n9xYdrctsWo/KKN3V5UlWS5wFqQSucPfvmVkBcKm7v9LVa929CSgxs0FAvZl90d0PtZmnFqgFKC8v1x5+mgy6ocPTI9INubAelVE6kspvsv4tMAa4I/n4KLCwOwtx9yNAA3BLd14nIiJnL5WCv97d/wvwMYC7/wY4t6sXmdng5J47ZtYPmAT8rAdZRUSkG1L5HPyp5LF0h0RxA79L4XWfB5YnX3sO8L/dXd9LFhHJkFQK/mmgHrjEzKqB24C/6upF7n4QuK5n8URE5Gx1WfDuvsLMGoGJJD4i+Ufu/kbkyUREpEdS2YMHeBv4sHl+Mytw93+NLJWIiPRYKh+TvA94CPgViR/dbv6iU3FnrxMRkXilsgd/P3C1u//fqMOIiEj6pPIxyfdIXGRMRERySGcXG/tW8u7PgQYz+zGJC4gB4O5/HXE2ERHpgc4O0Zyf/Puvydu5pPAFJxERyQ6dXWxM128XEclhqRyDFxGRHKSCFxEJVJcFn/xFp7bPnfU14kVEJDNS2YPfYGYDmh+Y2XBgQ3SRREQkHVIp+P9OouTPM7MyYDXwJ9HGEhGRnkrlYmM/Tv5o9lYSH538I3d/O/JkIiLSI5190el/0fpHsgeQ+NLTfWaGu/9F1OFEROTsdbYH3/bXcRujDCIiIunV2RedlgOY2WeBj5M/oE3yF5o+k5l4IiJytlI5ybod6NficT/g+WjiiIhIuqRS8H3d/Vjzg+T9/tFFEhGRdEil4I+bWWnzg+RHJU9EF0lERNIhlR/8mAOsNrPDycefByqiiyQiIumQyufg95jZNcDVJH6u72fufiryZCIi0iOp/uj21cBwoC9wXfJz8HXRxRIRkZ5K5Ue3HwJuJFHw/wRMAV4EVPAiIlkslZOstwETgf9w9zuBUehz8CIiWS+VQzQn3P13ZnY6eVXJ94ErI87VK9U+9TC7GraRl5/PkKFFzH10AecNGBh3LImItnd6zJs3jw0bNnDuuefyhS98gR/+8IcMGjQo7lhZIZU9+L1mNghYQuJyBa8Cr0SaqpcqHTOBJesaqK3fwWWFV7JyydNxR5IIaXunx+TJkzl06BAHDx5k2LBhPPbYY3FHyhqpfIpmdvLuIjPbDAxw94PRxgpfdXU1dXV1DB06lMGDB1NWVkb5V79+Zvq1o8rYuXVjjAklnVYsXsDz61cz+NIhDLzgIoaNKOb2O2efma7tnZr21uPiJz/9+ejRo0ezZs2aGBNml1ROsm5394kA7v5u2+ek+xobG1m1ahX79u3j9OnTlJaWUlZW1mqeLWtXMmHK9JgSSjq99doBGjat45k122hqamL2bZMZNqK41Tza3l1LZT0uW7aMigp9TadZZ5cL7kvikgQXm9kFJD4DD4nLBg/JQLZg7dy5kxkzZtC/f+KKD9OmTWs1fcXiBfTJy2Pi1JlxxJM0O9S4m7ETp9C3X2J7j7np5lbTtb1T09V6rK6uJi8vj8rKyjjiZaXO9uDvJvEt1iEkjr03F/yHwMKIcwXPzNp9fuu659j9k208sXR1h/NI7tH2To+O1tHy5cvZuHEj27dv13psocOTrO7+N+5+BTDX3a909yuSt1HuXtPVwGY21Mx2mNkbZvaamd2f1uQ5bPz48dTX13PixAmOHj3Khg2Jn7jds/MFnltawyM1y8/spUjuG1k+mpe2b+Lkxyf46PgxXm7YCmh7d1dH63Hz5s08/vjjrF+//sx/FUtCKh+T/A8zO9/dj5rZXwGlwKPu/moXrzsN/Fd3f9XMzgcazWybu7/e09C5rrS0lIqKCkpKSigsLGTcuHEA1FQ/yKlTn/DtuxLHEK8dVcach56IM6qkwVXDi5lwy3TumTmJS4Zczsiy6wFt7+7qaD3ee++9nDx5ksmTJwOJE62LFi2KM2rWSKXgv+vuq83sBuBm4CngGeD6zl7k7v8O/Hvy/lEzewO4DOj1BQ9QVVVFVVUVAPPnzwdg+eZdMSaSKFXePYfKu+cAULfwSUDb+2y0tx7feeedOCNltVQKvin591bgGXf/RzOb352FmFkRcB2wu51ps4BZAAUFBd0ZNucUPfDjdp8/8uJbWH4/Bn7Q9lcSW3v3+7emPdOk4Z/L+jFzMWNH2xrgyIHDWH4/tvTJ7PbOxfUInbxvmtdjJ+saonnf5IpUCv7fzGwxMAl43Mw+Q2pfkALAzM4DfgTMcfcP205391qgFqC8vNzbTu8NBt2gs/69ibZ3emg9di2Vov7PwBbgFnc/AlwIzEtlcDPLJ1HuK9x97VmnFBGRbkvlm6wfAWtbPD5zbL0zlvis0lLgDXf/656EFBGR7kv5UMtZGAt8Hfiyme1P3r4a4fJERKSFVH/wo9vc/UU+/XKUiIhkWJR78CIiEiMVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBd8D8+bN45prrqG4uJgZM2Zw5MiRuCOJSA+F9L5WwffA5MmTOXToEAcPHmTYsGE89thjcUcSkR4K6X2dF3eAXFFdXU1dXR1Dhw5l8ODBlJWVMXfu3DPTR48ezZo1a2JMKCLdFfr7WgWfgsbGRlatWsW+ffs4ffo0paWllJWVtZpn2bJlVFRUxJRQRLqrN7yvVfAp2LlzJzNmzKB///4ATJs2rdX06upq8vLyqKysjCOeiJyF3vC+VsGnyMzafX758uVs3LiR7du3dziPiGSn0N/XkZ1kNbNlZva+mR2KahmZMn78eOrr6zlx4gRHjx5lw4YNAGzevJnHH3+c9evXn9kLEJHc0Bve11Huwf8dUAPURbiMjCgtLaWiooKSkhIKCwsZN24cAPfeey8nT55k8uTJQOKEzKJFi+KMKiIp6g3v68gK3t1/amZFUY2faVVVVVRVVQEwf/58AN55550YE4lIT4X+vo79GLyZzQJmARQUFMSc5lNFD/y4w2lHXnwLy+9HzQcdzwPw7vdvTXcsEemhjt7bqb6vIXfe27EXvLvXArUA5eXlHnOclAy6IXfPqotI+0J8X+ubrCIigVLBi4gEKsqPSa4EXgauNrNfmtk3o1qWiIj8vig/RfPHUY0tIiJd0yEaEZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFA9ZqCX716NSNGjOCcc85h7969cccRkV7ku9/9LsXFxZSUlPCVr3yFw4cPZ2S5vabgv/jFL7J27VrGjx8fdxQR6WXmzZvHwYMH2b9/P1OnTuWRRx7JyHLzMrKUDKuurqauro6hQ4cyePBgysrKmDt3btyxRKQX6Kp/jh8/jpllJEtwBd/Y2MiqVavYt28fp0+fprS0lLKysrhjiUgv0Fn/VFVVUVdXx8CBA9mxY0dG8gR3iGbnzp3MmDGD/v37M2DAAKZNmxZ3JBHpJTrrn+rqat577z0qKyupqanJSJ7gCh7I2H/+iIi01VX/3HHHHfzoRz/KSJZIC97MbjGzN83sHTN7IMplNRs/fjz19fWcOHGCo0ePsmHDhkwsVkSkw/55++23z8yzfv16rrnmmozkiewYvJn1ARYCk4FfAnvMbL27vx7VMgFKS0upqKigpKSEwsJCxo0bB0B9fT333Xcfv/71r7n11lspKSlhy5YtUUYRkV6mo/554IEHePPNNznnnHMoLCxk0aJFGckT5UnWLwHvuPvPAcxsFTAdiLTgIXEyo6qqCoD58+cDMGPGDGbMmBH1okWkl2uvfzJ1SKYtc/doBja7DbjF3e9KPv46cL2739tmvlnArOTDq4E30xxlCNAE/CrF+S8GPkhzhnSPmQsZoxhTGbNzvFwZM46M3e2fs1Ho7oPbmxDlHnx7Zxp+718Td68FaiPM0S1mttfdy7N5zFzIGMWYypid4+XKmLmQMd2iPMn6S2Boi8eXA5n5fq6IiERa8HuAq8zsCjM7F/gasD7C5YmISAuRHaJx99Nmdi+wBegDLHP316JaXhpFcbgo3WPmQsYoxlTG7BwvV8bMhYxpFdlJVhERiVeQ32QVEREVvIhIsFTwkvXMrMjMDmXreFGNmQu0bbKbCl5EJFAq+AiZ2TozazSz15Lf2O0VY0aREcgzs+VmdtDM1phZ/ywbL+1j5sK2Tup12yZnuLtuEd2AC5N/+wGHgIt6w5gRjFdE4lvQY5OPlwFzs2W8CMfMhW3dK7dNrty0Bx+tvzCzA8AuEt/qvaqXjBlFxvfc/aXk/X8Absiy8aIYMxe2NfTObZMTgvvJvmxhZjcCk4Ax7v6RmTUAfUMfM4qMSW2/sNHTL3Cke7y0jpkL27qFXrVtcon24KMzEPhN8o10DTC6l4wZRUaAAjMbk7z/x8CLWTZeusfMhW3drLdtm5yhgo/OZhIndg4C3yPxn8S9YcwoMgK8AfxpctwLgWeybLx0j5kL27pZb9s2OUOXKhARCZT24EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCl5xkZv8cwZhFZnZHN1/zYBfT/8nMBvUsmcjZ0cckRZKS3/Sc6+5Tu/GaY+5+XjvPG4n31+/SGFGkW7QHLznJzI4l/95oZg3JKwT+zMxWJMsVM3vXzB43s1eStz9IPv93ZnZb27GA7wPjzGy/mf1lm+V93sx+mpx2yMzGmdn3gX7J51Yk/wvgDTP7W+BVYGgyw8Utpi1JXslxq5n1S479n5JXOXzZzJ60Xnrtckk/FbyE4DpgDjAcuBIY22Lah+7+JaAGWNDFOA8AO929xN3/Z5tpdwBb3L0EGAXsd/cHgBPJ+SuT810N1Ln7de7+izZjXAUsdPcRwBFgZvL5HwL3uPsYoCnF/80iXVLBSwhecfdfJg+H7CdxedhmK1v8HdP2hd2wB7jTzOYDI939aAfz/cLdO7oEwL+4+/7k/UagKHl8/nx3bz6n8GwPMoq0ooKXEJxscb+J1ldJ9Xbunyb5//3k4Zxzu1qAu/8UGA/8G/D3ZvaNDmY93s2c1tWyRc6WCl5CV9Hi78vJ++8CZcn704H85P2jwPntDWJmhcD77r4EWAqUJiedMrP89l6TCnf/DXDUzJqv7Pi1sx1LpC0VvITuM2a2G7gfaD5xugSYYGavANfz6V73QeC0mR1oe5IVuBHYb2b7SBw7/5vk87XAQTNb0YOM3wRqzexlEnv0v+3BWCJn6GOSEiwzexcod/cP4s7SGTM7z92bPxX0APB5d78/5lgSAP2ik0j8bjWz75B4P/4C+LN440gotAcvIhIoHYMXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQnU/wfHcGuknw1sXQAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((2,2),10,3.5,alpha=0.3))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "But this isn't a sub-run, because it doesn't start and end with the same stack:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAdAUlEQVR4nO3de3RU9b338fcXEgUq4A0vKCS6FBUU0yStchDQAhYqDzbFPlTpzVMPWuqF9sGWihQE4wXpORyLF0KxhTaCBwUEW25aouhRhMilWKy6WqoWbWtbalBUiN/njz0giZlkkpk9lz2f11qzZmZffvvL3syHzb78trk7IiISPe0yXYCIiIRDAS8iElEKeBGRiFLAi4hElAJeRCSiCjJdwKGOPfZYLy4uznQZGfPO+/syXYJI3uvSoTDTJbRKbW3t2+7eralxWRXwxcXFbNq0KdNlZMzjv/tLpksQyXtDeh+f6RJaxcz+FG+cDtGIiESUAl5EJKIU8CIiEaWAFxGJKAW8iEhEKeBFRCJKAS8iElEKeBGRiFLAi4hEVFbdySr5qWrmLTxXs5aCwkK69yhmwq2zOKJL10yXJZLztAcvGVfabxBzl9VQtXQdJxWdysK5d2e6JJFI0B68pFX1nFk8vnwx3U7oTtejjqFXn758+cpxB8efdW4Z69c8lsEKRaJDAS9p8/KLW6lZuYz7Hl5LfX094y4bSq8+fRtMs3rJQgYNvzRDFYpEiwJe0mZ77Qb6Dx5Oh46dAOh30ecbjK+eM4v2BQUMHjEqE+WJRI4CXtLKzJocvmbZQ2x4ci0z5i2OO42ItE6oJ1nNbKeZ/dbMtphZ/nb0LgCcU34+zzyxkg/e38t77+7h2Zo1AGxc/xsemjebabPnH9y7F5HkpWMP/iJ3fzsNy5Esd3rvvgwadinXjBrCcd1P5pyy8wCYXXkT+/Z9yA+uGg0EJ1rHT5mRyVJFIkGHaCStxlw9njFXjwdgwT13ATB/1XOZLEkkssIOeAfWmJkDc9y9qvEEZjYWGAvQs2fPkMuRTLhqQdNH53Zv3YUVdmR1++aP3v306+VhlCUSeWEHfH9332VmxwFrzewld3/q0AlioV8FUF5e7iHXI1nkyAvGZLoEkUgL9SSru++Kvf8VWAp8NszliYjIx0ILeDP7lJl1PvAZuBjYHtbyRESkoTAP0RwPLI1d01wAPOjuq0JcnoiIHCK0gHf3PwDnhtW+iIg0T71JiohElAJeRCSiFPAiIhGlgBcRiSgFvIhIRCngRUQiSgEvIhJRCngRkYhSwIuIRJQCXkQkohTwIiIRpYAXEYkoBbyISEQp4EVEIkoBLyISUQp4EZGIUsCLiESUAl5EJKIU8CIiEaWAFxGJKAW8iEhEKeBFRCJKAS8iElEKeBGRiFLAi4hEVEGmC5DcUjXzFp6rWUtBYSHdexQz4dZZHNGla6bL+oRcqTPbaT3mNu3BS6uU9hvE3GU1VC1dx0lFp7Jw7t2ZLqlJuVJnttN6zG3ag5e4qufM4vHli+l2Qne6HnUMvfr05ctXjjs4/qxzy1i/5rEMVhjIlTqzndZj9CjgpUkvv7iVmpXLuO/htdTX1zPusqH06tO3wTSrlyxk0PBLM1RhIFfqzHZaj9GkgJcmba/dQP/Bw+nQsRMA/S76fIPx1XNm0b6ggMEjRmWivINypc5sp/UYTQp4icvMmhy+ZtlDbHhyLTPmLY47TTrlSp3ZTusxekI/yWpm7c1ss5np4F0OOaf8fJ55YiUfvL+X997dw7M1awDYuP43PDRvNtNmzz+4t5dJuVJnttN6jKZ07MHfAOwAuqRhWZIip/fuy6Bhl3LNqCEc1/1kzik7D4DZlTexb9+H/OCq0UBw4m38lBmqM8dpPUaTuXt4jZudDMwHKoHvufuI5qYvLy/3TZs2hVZPtnv8d3/JdAlxLbjnLjp2+lSDqyoSddWC5LbpT79envC0ydQpH8vn9Tik9/GZLqFVzKzW3Zv8kYS9Bz8L+D7QOd4EZjYWGAvQs2fPkMuRlsQL491bd2GFHVndvuWwbk0gt0Vz/2AkWmfYNeYCrcfoCy3gzWwE8Fd3rzWzC+NN5+5VQBUEe/Bh1SPJOfKCMZkuISG5Ume203qMhjBPsvYHRprZTmAR8Dkz+2WIyxMRkUOEFvDu/kN3P9ndi4GvAL9x96+GtTwREWlIfdGIiERUWm50cvcaoCYdyxIRkYD24EVEIkoBLyISUQp4EZGIUsCLiESUAl5EJKIU8CIiEaWAFxGJKAW8iEhEKeBFRCJKAS8iElEKeBGRiFLAi4hElAJeRCSiFPAiIhHVYsCb2ZcTGSYiItklkT34HyY4TEREskjcB36Y2XDgC8BJZnb3IaO6APvDLkxERJLT3BOddgGbgJFA7SHD64DvhlmUiIgkL27Au/tWYKuZPeju+9JYk4iIpEAiz2T9rJlNBYpi0xvg7n5qmIWJiEhyEgn4eQSHZGqB+nDLERGRVEkk4P/l7itDr0RERFKquatoSmMf15nZXcAS4IMD4939hZBrExGRJDS3B//jRt/LD/nswOdSX46IiKRKc1fRXJTOQiQcVTNv4bmatRQUFtK9RzETbp3FEV26ZrqsnJML61E1SmOJdFXwvSZe3zKzknQUKMkp7TeIuctqqFq6jpOKTmXh3Ltbnkk+IRfWo2qUxhI5yVoee62Ifb8E2AhcY2aL3X1GWMVJ61TPmcXjyxfT7YTudD3qGHr16cuXrxx3cPxZ55axfs1jGawwN+TCelSNkohEAv4YoNTd9wCY2RTgYWAgwaWTCvgs8PKLW6lZuYz7Hl5LfX094y4bSq8+fRtMs3rJQgYNvzRDFeaGXFiPqlESlUjA9wQ+POT7PqDI3fea2Qdx5pE02167gf6Dh9OhYycA+l30+Qbjq+fMon1BAYNHjMpEeTkjF9ajapREJRLwDwLPmdmjse//B1hoZp8CfhdaZdJqZtbk8DXLHmLDk2uZMW9x3GnkY7mwHlWjJKLFk6zuPh34D2A38C/gGnef5u7vuvuYePOZWQcze97MtprZi2Z2S+rKlsbOKT+fZ55YyQfv7+W9d/fwbM0aADau/w0PzZvNtNnzD+5NSXy5sB5VoySquRudurj7O2Z2NPDH2OvAuKPd/R8ttP0B8Dl332NmhcDTZrbS3Z9LSeXSwOm9+zJo2KVcM2oIx3U/mXPKzgNgduVN7Nv3IT+4ajQQnNgaP0WnTeLJhfWoGiVRzR2ieRAYQXAi1Yl1MnbIe7Odjbm7A3tiXwtjL0+yXmnGmKvHM+bq8QAsuOcuAOav0r+nrZUL61E1SiKau9FpROz9lLY2bmbtCf6BOA24x903NDHNWGAsQM+ePdu6qLx01YJNccft3roLK+zI6vbxpwH46dfLmx2fL+Kty2xaj6pRWqvFk6wWnAUZA5zi7tPNrCdwgrs/39K87l4PlJjZkcBSMzvb3bc3mqYKqAIoLy/XHn6KHHlB3NMj0gq5sB5Vo8STyDNZ7wX6AVfEvtcB97RmIe6+G6gBhrVmPhERabtEAv48d/8O8D6Au/8TOKylmcysW2zPHTPrCAwBXkqiVhERaYVEroPfFzuW7hAEN/BRAvOdCMyPzdsO+B93133JIiJpkkjA3w0sBY4zs0rgMuDmlmZy923Ap5MrT0RE2qrFgHf3ajOrBQYTXCL5RXffEXplIiKSlET24AFeAd45ML2Z9XT310KrSkREkpbIZZLXAVOAvxA8dPvAjU59m5tPREQyK5E9+BuAM9z972EXIyIiqZPIZZKvE3QyJiIiOaS5zsa+F/v4B6DGzH5F0IEYAO7+nyHXJiIiSWjuEE3n2PtrsddhJHCDk4iIZIfmOhtT/+0iIjkskWPwIiKSgxTwIiIR1WLAx57o1HhYm/uIFxGR9EhkD36FmXU58MXMegMrwitJRERSIZGAv40g5I8wszJgMfDVcMsSEZFkJdLZ2K9iD81eQ3Dp5Bfd/ZXQKxMRkaQ0d6PTT2j4kOwuBDc9XWdmuPv1YRcnIiJt19wefOOn49aGWYiIiKRWczc6zQcws08B78ceoE3sCU2Hp6c8ERFpq0ROsj4BdDzke0fg8XDKERGRVEkk4Du4+54DX2KfO4VXkoiIpEIiAf+umZUe+BK7VHJveCWJiEgqJPLAj/HAYjPbFft+IjA6vJJERCQVErkOfqOZnQmcQfC4vpfcfV/olYmISFISfej2GUBvoAPw6dh18AvCK0tERJKVyEO3pwAXEgT8r4HhwNOAAl5EJIslcpL1MmAw8Ja7Xwmci66DFxHJeokcotnr7h+Z2f5Yr5J/BU4Nua68VDXzFp6rWUtBYSHdexQz4dZZHNGla6bLkpBoe6eG1mN8iezBbzKzI4G5BN0VvAA8H2pVeaq03yDmLquhauk6Tio6lYVz7850SRIibe/U0HqML5GraMbFPt5vZquALu6+Ldyyoq+yspIFCxbQo0cPunXrRllZGeVf+NrB8WedW8b6NY9lsEJJpeo5s3h8+WK6ndCdrkcdQ68+ffnyleMOjtf2TozWY+skcpL1CXcfDODuOxsPk9arra1l0aJFbN68mf3791NaWkpZWVmDaVYvWcig4ZdmqEJJpZdf3ErNymXc9/Ba6uvrGXfZUHr16dtgGm3vlmk9tl5z3QV3IOiS4FgzO4rgGngIug3unobaImv9+vVUVFTQqVPQ48PIkSMbjK+eM4v2BQUMHjEqE+VJim2v3UD/wcPp0DHY3v0u+nyD8dreidF6bL3m9uCvJriLtTvBsfcDAf8OcE/IdUWemTU5fM2yh9jw5FpmzFscdxrJPdreqaH12DpxT7K6+3+7+ynABHc/1d1Pib3OdffZLTVsZj3MbJ2Z7TCzF83shpRWnsMGDhzI0qVL2bt3L3V1daxYETziduP63/DQvNlMmz3/4F6K5L5zys/nmSdW8sH7e3nv3T08W7MG0PZuLa3H1kvkMsm3zKyzu9eZ2c1AKXCru7/Qwnz7gf/n7i+YWWeg1szWuvvvki0615WWljJ69GhKSkooKipiwIABAMyuvIl9+z7kB1cFXf2cdW4Z46fMyGSpkgKn9+7LoGGXcs2oIRzX/WTOKTsP0PZuraTW40cfcdjf3+bDbselrqA334QTT0xdeyFIJOAnu/tiM7sA+DwwE7gPOK+5mdz9TeDN2Oc6M9sBnATkfcADTJo0iUmTJgEwdepUAOavei6DFUmYxlw9njFXjwdgwT13AdrebdHW9dj3u1fR4c+v8/z/rIZ2iVwd3oLXX4deveDHP4Zx41qePkMSCfj62PslwH3u/qiZTW3NQsysGPg0sKGJcWOBsQA9e/ZsTbM5p3jir5ocvvvpl7HCjnR9u/FTEhvaecclKa9pSO/js77NXKwx3rYG2L11F1bYkdXt07u9c3E9QjO/m9asx6+Nhm98gyEvPQOXXZZ8odOnQ309XJL632QqJRLwfzazOcAQ4E4zO5zEbpACwMyOAB4Bxrv7O43Hu3sVUAVQXl7ujcfngyMvGJPpEiSNtL1To1XrccwYuOMO+NGPoKIC2rdv+4JffRUeeAC+/W0oKmp7O2mQSFD/X2A1MMzddwNHAzcm0riZFRKEe7W7L2lzlSIiyWjfPtjr3rEDqquTa2vqVDjsMIgdYs1mLQa8u7/n7kvc/ZXY9zfdfU1L81lwrdI8YIe7/2fypYqIJOFLX4LSUpgyBT78sG1tbN8ODz4I118PJ5yQ2vpCkIKzDXH1B74GfM7MtsReXwhxeSIi8ZnBrbfCzp0wb17b2pg8GTp3hu9/P6WlhSXRB360mrs/zcc3R4mIZN6wYdC/fxD03/wmdOyY+LwbN8KyZXDLLXD00aGVmEph7sGLiGQXM6ishF274N57WzfvzTfDMcfA+PHh1BYCBbyI5JdBg2Do0OCqmrq6xOZ56ilYswYmToQuXcKtL4UU8CKSfyor4e23Ydaslqd1D66Y6d4dvvOd8GtLIQW8iOSfz3wGvvhFmDkT/vGP5qddtQqefjo4RNOaY/ZZQAEvIvlp+vTgEM2MZvr/cQ+CvbgYvvWttJWWKgp4EclPZ58Nl18Od98Nb73V9DRLlsALL3x8c1OOUcCLSP665ZbgpqfbbvvkuPr64Lr3M8+Er341/bWlgAJeRPLXaafBlVfCnDnw2msNxz34YNC1wbRpyfVdk0EKeBHJb5MnB+/Tpn087MMPg8MyJSUwKncfAaiAF5H81rNn0DPkz38OL78cDHvgAfjDH4LLKVPRf3yG5G7lIiKp8sMfwuGHBx2R7d0bXGHzb/8Gw4dnurKkhNYXjYhIzjj+eLjhBrj9djjppKArg+rqoGuDHKY9eBERgBtvhK5d4Sc/gSFD4MILM11R0hTwIiIARx0F5eXBCdbLL890NSmhgBcRgaDLgo0bgxuaFi7MdDUpoYAXEQG4666g64Lrr4fHH4d16zJdUdIU8CIib70VdFnwla8EV9CcdFLQg6R7pitLigJeROT22+GDD4KuCzp0CG5+evZZ+PWvM11ZUhTwIpLfXnsN7r8/eITf6acHw/793+HUU4OeJD/6KKPlJUMBLyL5bfr04P1HP/p4WGFh0FXBli3wyCMZKSsVFPAikr9eeQV+9jO4+uqgy4JDXXEF9O4dBP/+/ZmpL0kKeBHJX1OmBF0U3HTTJ8e1bx/s3b/0Evzyl+mvLQUU8CKSn377W1i0KLgs8oQTmp6mogLKyj7uNz7HKOBFJD9NngydOwddFMRjBrfeCjt3wk9/mrbSUkUBn4Qbb7yRM888k759+1JRUcHu3bszXZKIJOL55+HRR2HCBDj66AajPvG7Pu88uOCCIOjfey9DBbeNAj4JQ4cOZfv27Wzbto1evXpx++23Z7okEUnEzTfDscfC+PGfGPWJ3/UddwT9wr/5Jtx7bwaKbTsFfIIqKys544wzGDJkCJdffjkzZ87k4osvpqAg6HH5/PPP54033shwlSLSoiefhLVrYeJEKu++O7Hf9cCBcPHFcMcd8M47Gf4DJE4Bn4Da2loWLVrE5s2bWbJkCRs3bvzENA888ADDc/zhACKR5x50QdC9O7Xnn9+633VlJfz97zBrVpqLbjsFfALWr19PRUUFnTp1okuXLowcObLB+MrKSgoKChgzZkyGKhSRhKxcCc88A5Mns37jxtb9rsvLg6tqZs4Mgj4HKOATZHGe7DJ//nwee+wxqqur404jIlngo4+CY++nnBJ0RUAbftfTp8OePTBjRjoqTlpoAW9mD5jZX81se1jLSJeBAweydOlS9u7dS11dHStWrABg1apV3HnnnSxfvpxOnTpluEoRadaSJbB5c9AFwWGHte133adPcIfrT34SnHTNcmHuwf8cGBZi+2lTWlrK6NGjKSkpYdSoUQwYMACAa6+9lrq6OoYOHUpJSQnXXHNNhisVkSbV1wddDpx1FsQOubT5dz11anDT0223pfkP0XqhPXTb3Z8ys+Kw2k+3SZMmMWnSJACmTp0KwKuvvprBikQkYdXVsGMHLF4cdEEQ06bf9WmnBYd45swJrqMvKgqr6qSFFvCJMrOxwFiAno07+8mg4om/ijtu99MvY4Udmf12/GkAdt5xSarLEpG2ePRRKC2FL30p7m870d81wM7Jk+EXvwj6i//2t1NdbcpkPODdvQqoAigvL8+Jx6cceYGulhHJKYsXw9/+Bu3iH5Vu1e+6Rw/44x/j92GTJXQVjYhEX7t2cPzxqW0zy8MdFPAiIpEV5mWSC4FngTPM7A0z+1ZYyxIRkU8K8yqay8NqW0REWqZDNCIiEaWAFxGJKAW8iEhEKeBFRCJKAS8iElEKeBGRiFLAi4hElAJeRCSiFPAiIhGlgBcRiSgFvIhIRCngRUQiSgEvIhJRCngRkYhSwIuIRJQCXkQkohTwIiIRpYAXEYkoBbyISEQp4EVEIkoBLyISUQp4EZGIUsCLiESUAl5EJKIU8CIiEZU3Ab948WL69OlDu3bt2LRpU6bLEZE8MnnyZPr27UtJSQkXX3wxu3btSsty8ybgzz77bJYsWcLAgQMzXYqI5Jkbb7yRbdu2sWXLFkaMGMG0adPSstyCtCwlzSorK1mwYAE9evSgW7dulJWVMWHChEyXJSJ5oKX8effddzGztNQSuYCvra1l0aJFbN68mf3791NaWkpZWVmmyxKRPNBc/kyaNIkFCxbQtWtX1q1bl5Z6IneIZv369VRUVNCpUye6dOnCyJEjM12SiOSJ5vKnsrKS119/nTFjxjB79uy01BO5gAfS9t8fEZHGWsqfK664gkceeSQttYQa8GY2zMx+b2avmtnEMJd1wMCBA1m6dCl79+6lrq6OFStWpGOxIiJx8+eVV145OM3y5cs588wz01JPaMfgzaw9cA8wFHgD2Ghmy939d2EtE6C0tJTRo0dTUlJCUVERAwYMAGDp0qVcd911/O1vf+OSSy6hpKSE1atXh1mKiOSZePkzceJEfv/739OuXTuKioq4//7701JPmCdZPwu86u5/ADCzRcClQKgBD8HJjEmTJgEwdepUACoqKqioqAh70SKS55rKn3QdkmnM3D2chs0uA4a5+1Wx718DznP3axtNNxYYG/t6BvD7FJfSHagH/pLg9McCb6e4hlS3mQs1htGmaszO9nKlzUzU2Nr8aYsid+/W1Igw9+CbOtPwiX9N3L0KqAqxjlYxs03uXp7NbeZCjWG0qRqzs71caTMXaky1ME+yvgH0OOT7yUB67s8VEZFQA34jcLqZnWJmhwFfAZaHuDwRETlEaIdo3H2/mV0LrAbaAw+4+4thLS+FwjhclOo2c6HGMNpUjdnZXq60mQs1plRoJ1lFRCSzInknq4iIKOBFRCJLAS9Zz8yKzWx7trYXVpu5QNsmuyngRUQiSgEfIjNbZma1ZvZi7I7dvGgzjBqBAjObb2bbzOxhM+uUZe2lvM1c2NYxebdtcoa76xXSCzg69t4R2A4ckw9thtBeMcFd0P1j3x8AJmRLeyG2mQvbOi+3Ta68tAcfruvNbCvwHMFdvafnSZth1Pi6uz8T+/xL4IIsay+MNnNhW0N+bpucELlH9mULM7sQGAL0c/f3zKwG6BD1NsOoMabxDRvJ3sCR6vZS2mYubOtD5NW2ySXagw9PV+CfsR/SmcD5edJmGDUC9DSzfrHPlwNPZ1l7qW4zF7b1Afm2bXKGAj48qwhO7GwDphP8lzgf2gyjRoAdwDdi7R4N3Jdl7aW6zVzY1gfk27bJGeqqQEQkorQHLyISUQp4EZGIUsCLiESUAl5EJKIU8CIiEaWAl5xkZv8bQpvFZnZFK+e5qYXxvzazI5OrTKRtdJmkSEzsTs8J7j6iFfPscfcjmhhuBL+vj1JYokiraA9ecpKZ7Ym9X2hmNbEeAl8ys+pYuGJmO83sTjN7PvY6LTb852Z2WeO2gDuAAWa2xcy+22h5J5rZU7Fx281sgJndAXSMDauO/Q9gh5ndC7wA9IjVcOwh4+bGenJcY2YdY21/JtbL4bNmdpflad/lknoKeImCTwPjgd7AqUD/Q8a94+6fBWYDs1poZyKw3t1L3P2/Go27Aljt7iXAucAWd58I7I1NPyY23RnAAnf/tLv/qVEbpwP3uHsfYDcwKjb8Z8A17t4PqE/wzyzSIgW8RMHz7v5G7HDIFoLuYQ9YeMh7v8YztsJG4Eozmwqc4+51cab7k7vH6wLgj+6+Jfa5FiiOHZ/v7O4Hzik8mESNIg0o4CUKPjjkcz0Ne0n1Jj7vJ/Z3P3Y457CWFuDuTwEDgT8DvzCzr8eZ9N1W1mktLVukrRTwEnWjD3l/NvZ5J1AW+3wpUBj7XAd0bqoRMysC/uruc4F5QGls1D4zK2xqnkS4+z+BOjM70LPjV9ralkhjCniJusPNbANwA3DgxOlcYJCZPQ+cx8d73duA/Wa2tfFJVuBCYIuZbSY4dv7fseFVwDYzq06ixm8BVWb2LMEe/b+SaEvkIF0mKZFlZjuBcnd/O9O1NMfMjnD3A1cFTQROdPcbMlyWRICe6CSSeZeY2Q8Jfo9/Ar6Z2XIkKrQHLyISUToGLyISUQp4EZGIUsCLiESUAl5EJKIU8CIiEfX/ARc6nyZKoGmqAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((2,2),11,3.5,alpha=0.3))\n", "ax.add_line(lines.Line2D([12.5,13.5],[1,2], color=\"red\"))\n", "ax.add_line(lines.Line2D([12.5,13.5],[2,1], color=\"red\"))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And this isn't a sub-run, because it pops a symbol from the starting/ending stack:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAda0lEQVR4nO3de3RU5b3/8feXiwoqojX6s0KCFxDLxZhEi0Xwmp6iFk9Wa6nSm8v+qJxirRUsbdQikoPxVD2tWCCsUklbpBWJJ0GLIoWKWoWkaIjaIsva2tpTa3+lRUQQ/P7+2EMMkMskmT2TeebzWmtWZmbvefaX2exPnjz7Zu6OiIiEp1emCxARkXgo4EVEAqWAFxEJlAJeRCRQCngRkUD1yXQBLR177LE+ZMiQTJcRlL/+691MlyDS7PgBh2W6hOA0NDS85e55rU3rUQE/ZMgQ6uvrM11GUO5ZvSXTJYg0u6F0WKZLCI6Z/aGtaRqiEREJlAJeRCRQCngRkUAp4EVEAqWAFxEJlAJeRCRQCngRkUAp4EVEAqWAFxEJVI86k1VyU21VJS89u5beffvyoRPyuXL6XPodMSDTZYlkPfXgJeNOKxrLjEUrmbGwjrxBQ3hi2cJMlyQSBPXgJa1WL51P/RMPMzDvBI446hgGDR3BBVdc0zy9YHghjetXZbBCkXCoBy9p8/qWJjate5Qbf/AwV986jz9u2XzQPBsee4jhZ43PQHUi4VEPXtLm1aZ6Ro29mEMO6wfAyDEX7jd99dL59Ordm+KLJmaiPJHgKOAlrcys1fc3Pl7DS8+tY2rl/W3OIyKdE+sQjZm9Zmabzex5M9OF3nPcKaPOYvPTq9m9613efedtXnx2LQAvb3ySX/58EdfcNr+5dy8i3ZeOHvwF7v5WGpYjPdygoSMoPO8S7pp6OUcfdyInjyoGYMV9t7N3924WzLwagILTz+CK62dnslSRIGiIRtKq9KqplF41FYBV1fcCUH7/6kyWJBKsuAPegcfNzIGF7l514AxmNgWYApCfnx9zOZIJ31vzSqvvb/v937G+79DYxvR9rr9oaBxliQQv7oAf6+5vmNlxwGoz+627P9lyhkToVwGUlJR4zPVIDzLw3MmZLkEkaLHuZHX3NxI/3wRqgLPjXJ6IiHwgtoA3s8PN7Mh9z4GPA01xLU9ERPYX5xDN8UBN4pjmPsBSd9c56CIiaRJbwLv7q8AZcbUvIiLt07VoREQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQC1SfTBUh2qa2q5KVn19K7b18+dEI+V06fS78jBmS6rINkS509nb7H7KYevHTKaUVjmbFoJTMW1pE3aAhPLFuY6ZJalS119nT6HrObevDSptVL51P/xMMMzDuBI446hkFDR3DBFdc0Ty8YXkjj+lUZrDCSLXX2dPoew6MevLTq9S1NbFr3KDf+4GGuvnUef9yy+aB5Njz2EMPPGp+B6j6QLXX2dPoew6QevLTq1aZ6Ro29mEMO6wfAyDEX7jd99dL59Ordm+KLJmaivGbZUmdPp+8xTAp4aZOZtfr+xsdreOm5dUytvL/NedIpW+rs6fQ9hif2IRoz621mm8xsZdzLktQ5ZdRZbH56Nbt3vcu777zNi8+uBeDljU/yy58v4prb5jf39jIpW+rs6fQ9hsncPd4FmH0DKAEGuPtl7c1bUlLi9fX1sdaTa+5ZvaXLn9230+3o405kYN7xHJ9/Ks88soy9u3fTf8BAAApOP4Mrrp/dbjvfW/NKl2sAuP6ioWmpM9el43u8oXRYqsqVBDNrcPeSVqfFGfBmNghYAlQA31DAp193Ar6lVdX3cmi//vsdVZGsuAO+pe7UKR+I63tUwKdeewEf9xj8fwM3AUe2NYOZTQGmAOTn58dcjnSkrTDe9vu/Y33foTGJsO5MIHdFe78wkq0z7hqzgb7H8MUW8GZ2GfCmuzeY2fltzefuVUAVRD34uOqR7hl47uRMl5CUbKmzp9P3GIY4d7KOBSaa2WvAMuBCM/tJjMsTEZEWYgt4d/+Wuw9y9yHAZ4Ffuvvn4lqeiIjsT2eyiogEKi0nOrn7OmBdOpYlIiIR9eBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCVSHAW9mVyTznoiI9CzJ9OC/leR7IiLSg7R5ww8zmwBcApxoZt9vMWkAsCfuwkREpHvau6PTG0A9MBFoaPH+duCGOIsSEZHuazPg3f0F4AUzW+ru76WxJhERSYFk7sl6tpnNAgoS8xvg7n5ynIWJiEj3JBPwPyQakmkA9sZbjoiIpEoyAf9Pd/9F7JWIiEhKtXcUTVHi6Voz+y9gBbBr33R3/03MtYmISDe014O/64DXJS2eO3Bh6ssREZFUae8omgvSWYjEo7aqkpeeXUvvvn350An5XDl9Lv2OGJDpsrJONnyP2VDjjBkzqKur45BDDuGUU07hRz/6EQMHDsx0WcFK5lIF32jlcY2ZFaajQOme04rGMmPRSmYsrCNv0BCeWLYw0yVlpWz4HrOhxtLSUpqammhsbGTYsGHMnTs30yUFLZmdrCWJR13i9aXARuBaM3vQ3e+MqzjpnIqKCqqrqxk8eDB5eXkUFxdzWsnE5ukFwwtpXL8qgxVmh9VL51P/xMMMzDuBI446hkFDR3DBFdc0T+8J32O21nhDVWXz9DFjxrB8+fIMVhi+ZAL+Q0CRu78NYGbfAZYD44kOnVTA9wANDQ0sW7aMTZs2sWfPHoqKiiguLt5vng2PPUTheRMyVGF2eH1LE5vWPcqNP3iY9/fu5a6vljFo6Ij95sn09xhKjYsXL2bSpEkZqjA3JBPw+cDuFq/fAwrcfaeZ7WrjM5Jm69evp6ysjP79+wMwceLE/aavXjqfXr17U3zRxNY+LgmvNtUzauzFHHJYPwBGjtn/WIKe8D2GUGNFRQV9+vRh8uTJmSgvZyQT8EuBZ83sfxKvPwk8YGaHAy/FVpl0mpm1+v7Gx2t46bl1TK28v8155APZ8D1mc41Llixh5cqVrFmzJuM1hq7Dnazufjvwf4FtwD+Ba919trvvcPc2f/2a2WFmtsHMXjCzF83sttSVLQcaP348NTU17Ny5k+3bt1NXF+0yeXnjk/zy54u45rb5zb0padspo85i89Or2b3rXd59521efHYt0LO+x2yucdWqVVRWVlJbW9v816bEp70TnQa4+7/M7Bjg94nHvmnHuPv/66DtXcCF7v62mfUFnjKzX7j7sympXPZTVFTEpEmTKCwspKCggHHjxgGw4r7b2bt7NwtmXg1AwelncMX1szNZao82aOgICs+7hLumXs7Rx53IyaOi/Rg96XvM5hqnTZvGrl27KC0tBaIdrQsWLMhIjbmgvSGapcBlRDtSncRFxlr8bPdiY+7uwNuJl30TD+9mvdKO8vJyysvLAZg1a1b03v2rM1hRdiq9aiqlV00FYFX1vUBy3+OJm+s59anH+dXUb6eslo/96B7+PLKYP5w1PiU1plNrNW7dujWTJeWc9k50uizx86SuNm5mvYl+QZwK3Ofuz7UyzxRgCkB+fn5XF5WThsx8pM1p257agvXtx1Fvnd5uG6/dcel+r7+35pVu13VD6bCUtpnq9lprs63vctvv/471fYfGDpb52h2Xwku/gJolFH3183DRRd2ukU2b4IEFcPPNUDosNTW2kInvsb3/s3BwjdI9He5ktWgvyGTgJHe/3czygf/j7hs6+qy77wUKzWwgUGNmI9296YB5qoAqgJKSEvXwU2TguTo6IRU69T1+5Svw3e9CeTlceCF0dwfiLbfAwIFw442pqzFDsqHGECVzT9YfAOcAVyVebwfu68xC3H0bsA74RGc+J5JVDjsMbr0VnnsO6uo6nr89zzwDjzwCN90UhbxIFyQT8B91968C7wK4+z+AQzr6kJnlJXrumFk/4GLgt92oVaTn+9KX4JRTot73++93rQ336K+A446Dr30tpeVJbkkm4N9LjKU7RMENJPM/9wSiSw03El3aYLW7r+xypSLZoG9fmD0bGhvh5z/vWhtr1sC6dVHIH354SsuT3JJMwH8fqAGOM7MK4CngPzv6kLs3uvuZ7j7a3Ue6u47Nk9zw2c/CyJHwne/Anj2d++y+3vvgwdGYvkg3JHOi00+Bm4C5wF+Af3f3B+MuTCRr9eoFt98OW7ZAdXXnPltXBxs2RGP5hx4aT32SM5LpwQO8QtSLrwV2JI6kEZG2XH45nHUW3HYb7Erykk3vvx8dEnnqqfDFL8Zbn+SEZK4Hfx3wV2A1sBJ4JPFTRNpiBnPmwB//CFVVyX3mZz+DzZujXwp9+8Zbn+SEZHrw1wOnufuIxHj6KHcfHXdhIlmvtBTGj4eKCtixo/159+yJxuxHjozG8EVSIJmAf53oImMi0hlmUbj/9a8wb1778y5ZAq+8EvX6eyU7cirSvvYuNvaNxNNXgXVm9gjRBcQAcPe7Y65NJPudey5MmACVlXDttXDUUQfPs2tXdGjl2WfDRF2vX1Knva7CkYnHH4nG3w9p8d6R8ZcmEog5c+Af/4C72+gTVVVFY/Vz5nT/8gYiLbR3sTFdv10kFYqK4FOfigL+uuvg2GM/mLZjRzSMc955cPHFmatRgqTBPpF0mD07CvPKyv3fnzcvGqOvqFDvXVJOAS+SDh/5CHzuc1Ggv/FG9N62bVHgT5gAY8dmtj4JUjLHwR/Tyntdvka8SM6aNSs6HHLOnOj13XdHY/P7XoukWDI9+DozG7DvhZl9BOjmtVBFctDJJ8OXvwyLFkF9PdxzD3z609EYvUgMkgn4/yQK+SPMrBh4EPhcvGWJBOrmm6FPn+iywu+8E43Ni8Skwzs6ufsjiZtmP050eOS/u3v37/UlkotOPBG+8IXo0MiJE+H09m+pKNId7Z3odC/73yR7ANFJT9eZGe6uOxGIdMXu3dHPzl5KWKST2uvB1x/wuiHOQkRywquvwk9+Eo27P/podGPtM8/MdFUSqPZOdFoCYGaHA+8mbqBN4u5OulC1SFfcdls0Bv/jH0eXMbj55ujeqyIxSGYn6xqgX4vX/YAn4ilHJGAvvxz13r/61ei4+JtuinrxzzyT6cokUMkE/GHu/va+F4nn/eMrSSRQt94K/fvDzJnR6+uug+OPj27R597+Z0W6IJmA32FmzQfqJg6V3BlfSSIB2rQJli+HG2744Fo0hx8O3/52dIPtNWsyWp6EKZmA/zrwoJmtN7P1wM+AafGWJRKYm2+Go4+GG2/c//2vfCW6wbZ68RKDZG66vREYDkwF/gM43d11RI1Isp5+Ohpr/+Y3D74e/KGHRndy2rABamszU58EK9mLjZ0GfAQ4E7jSzL4QX0kiAXGPeufHHw/T2vjD94tfhKFD4ZZbohtvi6RIMhcb+w5wb+JxAXAnoNvOiCTjiSfgV7+KQv7ww1ufp0+f6PDJzZujG2+LpEgyPfhPAxcB/+vuVwNnoOPgRTq2r/eenw9TprQ/76RJMGpUNFyjM1wlRZIJ+J3u/j6wJ3FVyTeBk+MtKzfNmDGD4cOHM3r0aMrKyti2bVumS5LuqK2FjRujwyMPPbhPtN/6/tSn2PbNb0Y33l6yJAPFZi9tN21LJuDrzWwgsIjocgW/ATbEWlWOKi0tpampicbGRoYNG8bcuXMzXZJ01fvvR0fODB0ajbG34qD1/cIL0Y23b7stuhG3JEXbTduSuZrkfySeLjCzVcAAd2+Mt6zwVVRUUF1dzeDBg8nLy6O4uJjp06c3Tx8zZgzLly/PYIXSLcuWQVMTPPAA9OmT/PquqIDSUli4EL6m6/kdSNtN5ySzk7X5DAx3f83dG1u+J53X0NDAsmXL2LRpEytWrGDjxo0HzbN48WImTJiQgeqk2957LxpLHz0aPvOZzq3viy6C88+Pgn7HjvTX3oNpu+m8NgPezA5L3K7vWDM72syOSTyGAB9OV4EhWr9+PWVlZfTv358BAwYwceL+ByVVVFTQp08fJk+enKEKpVuWLIGtW+H226FXr86tb7Mo3N98E+69N0P/gJ5J203ntTdE8xWis1g/TDT2vu+W7/8C7ou5ruCZWavvL1myhJUrV7JmzZo255EebNeu6C5NZ58Nn/xk89udWt8f+xhccgnceSdcey0MHJiOyrOCtpvOabMH7+7fc/eTgOnufrK7n5R4nOHu8zpq2MwGm9laM3vZzF40s+tTWnkWGz9+PDU1NezcuZPt27dTVxfd4nbVqlVUVlZSW1tL//66nltWWrgQXn896oUngqZL63vOnOiG3Hffne5/QY+l7abzOtzJCvyvmR3p7tvN7GagCJjj7r/p4HN7gBvd/TdmdiTQYGar3f2l7had7YqKipg0aRKFhYUUFBQwbtw4AKZNm8auXbsoLS0Foh1GCxYsyGSp0hk7dkTBfv750Vh6QpfW95lnRjfkvuee6KqTeXnp/tf0ONpuOi+ZgL/F3R80s3OBfwO+C8wHPtreh9z9L8BfEs+3m9nLwIlAzgc8QHl5OeXl5QDMmjULgK1bt2awIum2738/GjuvqWnuve/TpfU9ezasWAF33AF33RVHxVlH203nJBPwexM/LwXmu/v/mNmsziwksWP2TOC5VqZNAaYA5Ofnd6bZrDNkZut37tn21Basbz/mvdX+nX1eu+PSOMqSVJkwAfbuhY99rM11DZ1c33feCeeck+pKs4q2m65LJuD/bGYLgYuBSjM7lOQvUoaZHQE8BHzd3f914HR3rwKqAEpKSnLyeqkDz9Ve/yAUFkaPDnRqfR94eWFppu2mY8kE9WeAx4BPuPs24BhgRjKNm1lfonD/qbuv6HKVIiLSacmcyfoOsKLF6+ax9fZYdKzSD4GX3V2HAoiIpFnSQy1dMBb4PHChmT2feFwS4/JERKSFZMbgu8Tdn+KDk6NERCTN4uzBi4hIBingRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYAXEQmUAl5EJFAK+G6YMWMGw4cPZ/To0ZSVlbFt27ZMlyQi3RTSdq2A74bS0lKamppobGxk2LBhzJ07N9MliUg3hbRd98l0AdmioqKC6upqBg8eTF5eHsXFxUyfPr15+pgxY1i+fHkGKxSRzgp9u1bAJ6GhoYFly5axadMm9uzZQ1FREcXFxfvNs3jxYiZNmpShCkWks3Jhu1bAJ2H9+vWUlZXRv39/ACZOnLjf9IqKCvr06cPkyZMzUZ6IdEEubNcK+CSZWavvL1myhJUrV7JmzZo25xGRnin07Tq2naxmttjM3jSzpriWkS7jx4+npqaGnTt3sn37durq6gBYtWoVlZWV1NbWNvcCRCQ75MJ2HWcP/n5gHlAd4zLSoqioiEmTJlFYWEhBQQHjxo0DYNq0aezatYvS0lIg2iGzYMGCTJYqIknKhe06toB39yfNbEhc7adbeXk55eXlAMyaNQuArVu3ZrAiEemu0LfrjI/Bm9kUYApAfn5+hqv5wJCZj7Q5bdtTW7C+/Zj3VtvzALx2x6WpLktEuqmtbTvZ7RqyZ9vOeMC7exVQBVBSUuIZLicpA8/N3r3qItK6ELdrnckqIhIoBbyISKDiPEzyAeDXwGlm9iczuyauZYmIyMHiPIrmyrjaFhGRjmmIRkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUDkT8A8++CAjRoygV69e1NfXZ7ocEckht9xyC6NHj6awsJCPf/zjvPHGG2lZbs4E/MiRI1mxYgXjx4/PdCkikmNmzJhBY2Mjzz//PJdddhmzZ89Oy3L7pGUpaVZRUUF1dTWDBw8mLy+P4uJipk+fnumyRCQHdJQ/O3bswMzSUktwAd/Q0MCyZcvYtGkTe/bsoaioiOLi4kyXJSI5oL38KS8vp7q6mqOOOoq1a9empZ7ghmjWr19PWVkZ/fv3Z8CAAUycODHTJYlIjmgvfyoqKnj99deZPHky8+bNS0s9wQU8kLY/f0REDtRR/lx11VU89NBDaakl1oA3s0+Y2e/MbKuZzYxzWfuMHz+empoadu7cyfbt26mrq0vHYkVE2syfV155pXme2tpahg8fnpZ6YhuDN7PewH1AKfAnYKOZ1br7S3EtE6CoqIhJkyZRWFhIQUEB48aNA6CmpobrrruOv/3tb1x66aUUFhby2GOPxVmKiOSYtvJn5syZ/O53v6NXr14UFBSwYMGCtNQT507Ws4Gt7v4qgJktAy4HYg14iHZmlJeXAzBr1iwAysrKKCsri3vRIpLjWsufdA3JHMjcPZ6GzT4NfMLdv5x4/Xngo+4+7YD5pgBTEi9PA36X4lI+DOwF/prk/McCb6W4hlS3mQ01xtGmauyZ7WVLm5mosbP50xUF7p7X2oQ4e/Ct7Wk46LeJu1cBVTHW0SlmVu/uJT25zWyoMY42VWPPbC9b2syGGlMtzp2sfwIGt3g9CEjP+bkiIhJrwG8EhprZSWZ2CPBZoDbG5YmISAuxDdG4+x4zmwY8BvQGFrv7i3EtL4XiGC5KdZvZUGMcbarGntletrSZDTWmVGw7WUVEJLOCPJNVREQU8CIiwVLAS49nZkPMrKmnthdXm9lA66ZnU8CLiARKAR8jM3vYzBrM7MXEGbs50WYcNQJ9zGyJmTWa2XIz69/D2kt5m9mwrhNybt1kDXfXI6YHcEziZz+gCfhQLrQZQ3tDiM6CHpt4vRiY3lPai7HNbFjXOblusuWhHny8vmZmLwDPEp3VOzRH2oyjxtfd/enE858A5/aw9uJoMxvWNeTmuskKwd2yr6cws/OBi4Fz3P0dM1sHHBZ6m3HUmHDgCRvdPYEj1e2ltM1sWNct5NS6ySbqwcfnKOAfiQ1pODAmR9qMo0aAfDM7J/H8SuCpHtZeqtvMhnW9T66tm6yhgI/PKqIdO43A7UR/EudCm3HUCPAy8MVEu8cA83tYe6luMxvW9T65tm6yhi5VICISKPXgRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQCpYCXrGRmz8TQ5hAzu6qTn/l2B9MfNbOB3atMpGt0mKRIQuJMz+nuflknPvO2ux/RyvtGtH29n8ISRTpFPXjJSmb2duLn+Wa2LnGFwN+a2U8T4YqZvWZmlWa2IfE4NfH+/Wb26QPbAu4AxpnZ82Z2wwHLO8HMnkxMazKzcWZ2B9Av8d5PE38BvGxmPwB+AwxO1HBsi2mLEldyfNzM+iXaPitxlcNfm9l/WY5eu1xSTwEvITgT+DrwEeBkYGyLaf9y97OBecB/d9DOTGC9uxe6+z0HTLsKeMzdC4EzgOfdfSawMzH/5MR8pwHV7n6mu//hgDaGAve5+whgG/CpxPs/Aq5193OAvUn+m0U6pICXEGxw9z8lhkOeJ7o87D4PtPh5zoEf7ISNwNVmNgsY5e7b25jvD+7e1iUAfu/uzyeeNwBDEuPzR7r7vn0KS7tRo8h+FPASgl0tnu9l/6ukeivP95D4v58YzjmkowW4+5PAeODPwI/N7AttzLqjk3VaR8sW6SoFvIRuUoufv048fw0oTjy/HOibeL4dOLK1RsysAHjT3RcBPwSKEpPeM7O+rX0mGe7+D2C7me27suNnu9qWyIEU8BK6Q83sOeB6YN+O00XAeWa2AfgoH/S6G4E9ZvbCgTtZgfOB581sE9HY+fcS71cBjWb2027UeA1QZWa/JurR/7MbbYk002GSEiwzew0ocfe3Ml1Le8zsCHffd1TQTOAEd78+w2VJAHRHJ5HMu9TMvkW0Pf4B+FJmy5FQqAcvIhIojcGLiARKAS8iEigFvIhIoBTwIiKBUsCLiATq/wOFCNf7YRNqTwAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((3,3),8,2.5,alpha=0.5))\n", "ax.add_line(lines.Line2D([7.5,8.5],[2,3], color=\"red\"))\n", "ax.add_line(lines.Line2D([7.5,8.5],[3,2], color=\"red\"))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The idea behind the conversion to CFG is that **sub-runs become sub-trees**. A sub-run that starts in state $q$ and ends in state $r$ is going to become a sub-tree that is rooted in the nonterminal $A_{qr}$.\n", "\n", "The whole run is a sub-run. It is generated by the nonterminal symbol $A_{q_1q_3}$, which we make the start symbol. We can picture it as below:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAYtklEQVR4nO3df3RX9Z3n8edbkpYggr+wGiFEtqBCCUiyRQ5otKCCZWV6wKVjWnc9ZYHDzoyZrl2ttgelMqcDzmzqhqEE6Q7ZQWSxkkGnSIISiy4gRIEFrTqnY8cOM/V0plRAQEjf+8f3BkOaHzfke7/ffD95Pc75nu+Pe+/nvr3X+8qH+9PcHRERCc8F2S5ARESSoYAXEQmUAl5EJFAKeBGRQCngRUQClZftAlq7/PLLvbi4OJG2Pzp5OpF2RUS6Mqh/fmJtNzU1/drdh7Q3rFcFfHFxMXv37k2k7W1v/SqRdkVEujJt9OcSa9vMftHRMO2iEREJlAJeRCRQCngRkUAp4EVEAqWAFxEJlAJeRCRQCngRkUAp4EVEAqWAFxEJVK+6klX6pponHmNXYwN5+fkUDivmgcerGDhocLbLEsl56sFL1k2YVM7qukZqNm3n6uEjWL/6yWyXJBIE9eAlo9atqmLb5o0MubKQwZdcxqgxJdx936Kzw68fV8qO+heyWKFIOBTwkjHvHtpP45Y6Vj7bQHNzM4vm3MaoMSXnjLP1ufWUz5iVpQpFwqKAl4w52LSbyVNn0L9gAACTbr3jnOHrVlXRLy+PqTNnZ6M8keAo4CWjzKzd3+vrNrD7lQaWrdnY4Tgi0j2JHmQ1s/fN7P+Z2T4zS+ZG75IzxpbdyGsvbeHUyRN8fPwYOxvrAdiz42U2rKlmSfXas717Eem5TPTgb3X3X2dgPtLLjRxdQvn0WSycPY0rCocytnQiANVLH+b06U94cN5cIHWgtXLxsmyWKhIE7aKRjKpYUEnFgkoAalcsB2Dti7uyWZJIsJIOeAfqzcyBVe5e03YEM5sPzAcoKipKuBzJhnm17e+dO7L/MJZfwNZ+ne+9e+resiTKEgle0gE/2d0Pm9kVQIOZ/czdf9p6hCj0awDKyso84XqkF7l4SkW2SxAJWqIHWd39cPT+IbAJ+GKS8xMRkU8lFvBmdqGZXdTyGbgdOJjU/ERE5FxJ7qL5HLApOqc5D3ja3V9McH4iItJKYgHv7j8HxiXVvoiIdE53kxQRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCZQCXkQkUAp4EZFAKeBFRAKlgBcRCVRetguQ3FLzxGPsamwgLz+fwmHFPPB4FQMHDc52Wb8nV+rs7bQcc5t68NItEyaVs7qukZpN27l6+AjWr34y2yW1K1fq7O20HHObevDSoXWrqti2eSNDrixk8CWXMWpMCXfft+js8OvHlbKj/oUsVpiSK3X2dlqO4VHAS7vePbSfxi11rHy2gebmZhbNuY1RY0rOGWfrc+spnzErSxWm5EqdvZ2WY5gU8NKug027mTx1Bv0LBgAw6dY7zhm+blUV/fLymDpzdjbKOytX6uzttBzDpICXDplZu7/X121g9ysNLFuzscNxMilX6uzttBzDk/hBVjPrZ2Zvmpl23uWQsWU38tpLWzh18gQfHz/GzsZ6APbseJkNa6pZUr32bG8vm3Klzt5OyzFMmejB3w+8DQzKwLwkTUaOLqF8+iwWzp7GFYVDGVs6EYDqpQ9z+vQnPDhvLpA68Fa5eJnqzHFajmEyd0+ucbOhwFpgKfBNd5/Z2fhlZWW+d+/eRGrZ9tavEmm3r6hdsZyCAReec1ZFXPNqe7ZOn7q3LPa4PalTPqXlmF7TRn8usbbNrMnd291Iku7BVwH/HbiooxHMbD4wH6CoqCjhcqQrHYXxkf2HsfwCtvbrOqy7E8jno7M/GHHrTLrGXKDlGL7EAt7MZgIfunuTmd3S0XjuXgPUQKoHn1Q90jMXT6nIdgmx5EqdvZ2WYxiSPMg6GbjLzN4HngG+ZGZ/k+D8RESklcQC3t2/7e5D3b0Y+Crwsrt/Lan5iYjIuXQvGhGRQGXkQid3bwQaMzEvERFJUQ9eRCRQCngRkUAp4EVEAqWAFxEJlAJeRCRQCngRkUAp4EVEAqWAFxEJlAJeRCRQCngRkUAp4EVEAqWAFxEJlAJeRCRQCngRkUB1GfBmdnec30REpHeJ04P/dszfRESkF+nwgR9mNgO4E7jazJ5sNWgQcCbpwkREpGc6e6LTYWAvcBfQ1Or3o8CfJlmUiIj0XIcB7+77gf1m9rS7n85gTSIikgZxnsn6RTN7FBgejW+Au/uIJAsTEZGeiRPwa0jtkmkCmpMtR0RE0iVOwP/W3bckXomIiKRVZ2fRTIg+bjez5cBzwKmW4e7+RsK1iYhID3TWg/+LNt/LWn124EvpL0dERNKls7Nobs1kIZKMmiceY1djA3n5+RQOK+aBx6sYOGhwtsvKObmwHFWjtBXnVgXfbOf1DTMbn4kCpWcmTCpndV0jNZu2c/XwEaxf/WTXE8nvyYXlqBqlrTgHWcui1/PR9y8De4CFZrbR3ZclVZx0z7pVVWzbvJEhVxYy+JLLGDWmhLvvW3R2+PXjStlR/0IWK8wNubAcVaPEESfgLwMmuPsxADNbDDwL3Ezq1EkFfC/w7qH9NG6pY+WzDTQ3N7Nozm2MGlNyzjhbn1tP+YxZWaowN+TCclSNElecgC8CPmn1/TQw3N1PmNmpDqaRDDvYtJvJU2fQv2AAAJNuveOc4etWVdEvL4+pM2dno7yckQvLUTVKXHEC/mlgl5n9bfT9PwDrzexC4K3EKpNuM7N2f6+v28DuVxpYtmZjh+PIp3JhOapGiaPLg6zu/j3gvwBHgN8CC919ibsfd/eKjqYzs/5m9rqZ7TezQ2b2WPrKlrbGlt3Iay9t4dTJE3x8/Bg7G+sB2LPjZTasqWZJ9dqzvSnpWC4sR9UocXV2odMgd//IzC4F/iF6tQy71N3/rYu2TwFfcvdjZpYPvGpmW9x9V1oql3OMHF1C+fRZLJw9jSsKhzK2dCIA1Usf5vTpT3hw3lwgdWCrcrEOm3QkF5ajapS4OttF8zQwk9SBVCe6yVir905vNubuDhyLvuZHL+9hvdKJigWVVCyoBKB2xXIA1r6ov6fdlQvLUTVKHJ1d6DQzer/mfBs3s36k/kB8Hljh7rvbGWc+MB+gqKjofGfVJ82r3dvhsCP7D2P5BWzt1/E4AE/dW9bp8L6io2XZm5ajapTu6vIgq6WOglQA17j798ysCLjS3V/valp3bwbGm9nFwCYz+4K7H2wzTg1QA1BWVqYefppcPKXDwyPSDbmwHFWjdCTOM1n/CpgE3BN9Pwqs6M5M3P0I0AhM7850IiJy/uIE/ER3/6/ASQB3/w3wma4mMrMhUc8dMysApgE/60GtIiLSDXHOgz8d7Ut3SAU38LsY010FrI2mvQD4P+6u65JFRDIkTsA/CWwCrjCzpcAc4DtdTeTuB4AbelaeiIicry4D3t3XmVkTMJXUKZJ/4O5vJ16ZiIj0SJwePMB7wEct45tZkbv/Y2JViYhIj8U5TfKPgcXAr0g9dLvlQqeSzqYTEZHsitODvx+41t3/NeliREQkfeKcJvkBqZuMiYhIDunsZmPfjD7+HGg0s78jdQMxANz9LxOuTUREeqCzXTQXRe//GL0+Q4wLnEREpHfo7GZjun+7iEgOi7MPXkREcpACXkQkUF0GfPREp7a/nfc94kVEJDPi9OCfN7NBLV/MbDTwfHIliYhIOsQJ+D8jFfIDzawU2Ah8LdmyRESkp+LcbOzvoodm15M6dfIP3P29xCsTEZEe6exCp//JuQ/JHkTqoqc/NjPc/U+SLk5ERM5fZz34tk/HbUqyEBERSa/OLnRaC2BmFwInowdoEz2h6bOZKU9ERM5XnIOsLwEFrb4XANuSKUdERNIlTsD3d/djLV+izwOSK0lERNIhTsAfN7MJLV+iUyVPJFeSiIikQ5wHflQCG83scPT9KmBuciWJiEg6xDkPfo+ZXQdcS+pxfT9z99OJVyYiIj0S96Hb1wKjgf7ADdF58LXJlSUiIj0V56Hbi4FbSAX8T4AZwKuAAl5EpBeLc5B1DjAV+Bd3vw8Yh86DFxHp9eLsojnh7r8zszPRXSU/BEYkXFefVPPEY+xqbCAvP5/CYcU88HgVAwcNznZZkhCt7/TQcuxYnB78XjO7GFhN6nYFbwCvJ1pVHzVhUjmr6xqp2bSdq4ePYP3qJ7NdkiRI6zs9tBw7FucsmkXRxx+a2YvAIHc/kGxZ4Vu3qoptmzcy5MpCBl9yGaPGlHD3fYvODr9+XCk76l/IYoWSTlrf6aHl2D1xDrK+5O5TAdz9/ba/Sfe9e2g/jVvqWPlsA83NzSyacxujxpScM87W59ZTPmNWliqUdNL6Tg8tx+7r7HbB/UndkuByM7uE1DnwkLptcGEGagvWwabdTJ46g/4FqTs+TLr1jnOGr1tVRb+8PKbOnJ2N8iTNtL7TQ8ux+zrrwS8gdRVrIal97y0B/xGwIuG6gmdm7f5eX7eB3a80sGzNxg7Hkdyj9Z0eWo7d0+FBVnf/gbtfAzzg7iPc/ZroNc7dq7tq2MyGmdl2M3vbzA6Z2f1prTyHjS27kdde2sKpkyf4+PgxdjbWA7Bnx8tsWFPNkuq1Z3spkvu0vtNDy7H74pwm+S9mdpG7HzWz7wATgMfd/Y0upjsD/Dd3f8PMLgKazKzB3d/qadG5buToEsqnz2Lh7GlcUTiUsaUTAahe+jCnT3/Cg/NSt/q5flwplYuXZbNUSQOt7/TQcuy+OAH/XXffaGZTgDuAJ4CVwMTOJnL3fwb+Ofp81MzeBq4G+nzAA1QsqKRiQSUAtSuWA7D2xV3ZLEkSpPWdHlqO3RMn4Juj9y8DK939b83s0e7MxMyKgRuA3e0Mmw/MBygqKupOszlnXm3bpyCmHNl/GMsvYGu/9oe3eOresiTKkgR0tK5B67u7tN2cvzgB/09mtgqYBvy5mX2WeBdIAWBmA4EfA5Xu/lHb4e5eA9QAlJWVedvhfcHFUyqyXYJkkNZ3emg5di1OUP9HYCsw3d2PAJcC34rTuJnlkwr3de7+3HlXKSIi3RbnStaPgedafT+7b70zljpXaQ3wtrv/ZU+KFBGR7ou9q+U8TAa+DnzJzPZFrzsTnJ+IiLQS94Ef3ebur/LpxVEiIpJhSfbgRUQkixTwIiKBUsCLiARKAS8iEigFvIhIoBTwIiKBUsCLiARKAS8iEigFvIhIoBTwIiKBUsCLiARKAS8iEigFvIhIoBTwIiKBUsCLiARKAS8iEigFvIhIoBTwIiKBUsCLiARKAS8iEigFvIhIoBTwIiKBUsCLiARKAS8iEqi8bBeQy2qeeIxdjQ3k5edTOKyYBx6vYuCgwdkuS0R6IKTtWj34HpgwqZzVdY3UbNrO1cNHsH71k9kuSUR6KKTtWj34mNatqmLb5o0MubKQwZdcxqgxJdx936Kzw68fV8qO+heyWKGIdFfo27UCPoZ3D+2ncUsdK59toLm5mUVzbmPUmJJzxtn63HrKZ8zKUoUi0l19YbtWwMdwsGk3k6fOoH/BAAAm3XrHOcPXraqiX14eU2fOzkZ5InIe+sJ2rYCPycza/b2+bgO7X2lg2ZqNHY4jIr1T6Nt1YgdZzexHZvahmR1Mah6ZMrbsRl57aQunTp7g4+PH2NlYD8CeHS+zYU01S6rXnu0FiEhu6AvbdZI9+L8GqoHaBOeRESNHl1A+fRYLZ0/jisKhjC2dCED10oc5ffoTHpw3F0gdkKlcvCybpYpITH1hu04s4N39p2ZWnFT7mVaxoJKKBZUA1K5YDsDaF3dlsyQR6aHQt+us74M3s/nAfICioqIsV/OpebV7Oxx2ZP9hLL+Arf06HgfgqXvL0l2WiPRQR9t23O0acmfbznrAu3sNUANQVlbmWS4nlounVGS7BBFJsxC3a13JKiISKAW8iEigkjxNcj2wE7jWzH5pZt9Ial4iIvL7kjyL5g+TaltERLqmXTQiIoFSwIuIBEoBLyISKAW8iEigFPAiIoFSwIuIBEoBLyISKAW8iEigFPAiIoFSwIuIBEoBLyISKAW8iEigFPAiIoFSwIuIBEoBLyISKAW8iEigFPAiIoFSwIuIBEoBLyISKAW8iEigFPAiIoFSwIuIBEoBLyISKAW8iEigFPAiIoHqMwH/ytbNzLvrZm7/wlW8c3BftssRkT7ku9/9LiUlJYwfP57bb7+dw4cPZ2S+fSbgiz9/HYt/8CPGlt2Y7VJEpI/51re+xYEDB9i3bx8zZ85kyZIlGZlvXkbmkmFLly6ltraWYcOGMWTIEEpLSxl/59ezXZaI9AHrVlWxbfNGhlxZyOBLLmPUmBKmLX/s7PDjx49jZhmpJbiAb2pq4plnnuHNN9/kzJkzTJgwgdLS0myXJSJ9wLuH9tO4pY6VzzbQ3NzMojm3MWpMCQCPPPIItbW1DB48mO3bt2eknuB20ezYsYOvfOUrDBgwgEGDBnHXXXdluyQR6SMONu1m8tQZ9C8YwIUDL2LSrXecHbZ06VI++OADKioqqK6uzkg9wQU8kLF//oiItNVV/txzzz38+Mc/zkgtiQa8mU03s3fM7O/N7KEk59Xi5ptvZtOmTZw4cYKjR4/y/PPPZ2K2IiKMLbuR117awqmTJ/j4+DF2NtYD8N57750dZ/PmzVx33XUZqSexffBm1g9YAdwG/BLYY2ab3f2tpOYJMGHCBObOncv48eMZPnw4N910EwCvbvsJK/7sEX77b//KdxZ9jX937Rf4/upnkixFRPqYkaNLKJ8+i4Wzp3FF4VDGlk4E4KGHHuKdd97hggsuYPjw4fzwhz/MSD1JHmT9IvD37v5zADN7BpgFJBrwkDqY8cgjjwDw6KOPAjBl2p1MmXZn0rMWkT6uYkElFQsqAahdsRwgY7tk2jJ3T6ZhsznAdHefF33/OjDR3f+ozXjzgfnR12uBd9JcSiHQDPwq5viXA79Ocw3pbjMXakyiTdXYO9vLlTazUWN38+d8DHf3Ie0NSLIH396Rht/7a+LuNUBNgnV0i5ntdfey3txmLtSYRJuqsXe2lytt5kKN6ZbkQdZfAsNafR8KZOb6XBERSTTg9wAjzewaM/sM8FVgc4LzExGRVhLbRePuZ8zsj4CtQD/gR+5+KKn5pVESu4vS3WYu1JhEm6qxd7aXK23mQo1pldhBVhERya4gr2QVEREFvIhIsBTw0uuZWbGZHeyt7SXVZi7QuundFPAiIoFSwCfIzOrMrMnMDkVX7PaJNpOoEcgzs7VmdsDMnjWzAb2svbS3mQvrOtLn1k3OcHe9EnoBl0bvBcBB4LK+0GYC7RWTugp6cvT9R8ADvaW9BNvMhXXdJ9dNrrzUg0/Wn5jZfmAXqat6R/aRNpOo8QN3fy36/DfAlF7WXhJt5sK6hr65bnJCcI/s6y3M7BZgGjDJ3T82s0agf+htJlFjpO0FGz29gCPd7aW1zVxY1630qXWTS9SDT85g4DfRhnQdcGMfaTOJGgGKzGxS9PkPgVd7WXvpbjMX1nWLvrZucoYCPjkvkjqwcwD4Hql/EveFNpOoEeBt4D9F7V4KrOxl7aW7zVxY1y362rrJGbpVgYhIoNSDFxEJlAJeRCRQCngRkUAp4EVEAqWAFxEJlAJecpKZ/d8E2iw2s3u6Oc3DXQz/iZld3LPKRM6PTpMUiURXej7g7jO7Mc0xdx/Yzu9Gavv6XRpLFOkW9eAlJ5nZsej9FjNrjO4Q+DMzWxeFK2b2vpn9uZm9Hr0+H/3+12Y2p21bwPeBm8xsn5n9aZv5XWVmP42GHTSzm8zs+0BB9Nu66F8Ab5vZXwFvAMOiGi5vNWx1dCfHejMriNr+99FdDnea2XLro/cul/RTwEsIbgAqgdHACGByq2EfufsXgWqgqot2HgJ2uPt4d/8fbYbdA2x19/HAOGCfuz8EnIjGr4jGuxaodfcb3P0XbdoYCaxw9zHAEWB29Pv/Aha6+ySgOeZ/s0iXFPASgtfd/ZfR7pB9pG4P22J9q/dJbSfshj3AfWb2KDDW3Y92MN4v3L2jWwD8g7vviz43AcXR/vmL3L3lmMLTPahR5BwKeAnBqVafmzn3LqnezuczRP/vR7tzPtPVDNz9p8DNwD8B/9vM7u1g1OPdrNO6mrfI+VLAS+jmtnrfGX1+HyiNPs8C8qPPR4GL2mvEzIYDH7r7amANMCEadNrM8tubJg53/w1w1Mxa7uz41fNtS6QtBbyE7rNmthu4H2g5cLoaKDez14GJfNrrPgCcMbP9bQ+yArcA+8zsTVL7zn8Q/V4DHDCzdT2o8RtAjZntJNWj/20P2hI5S6dJSrDM7H2gzN1/ne1aOmNmA9295aygh4Cr3P3+LJclAdATnUSy78tm9m1S2+MvgP+c3XIkFOrBi4gESvvgRUQCpYAXEQmUAl5EJFAKeBGRQCngRUQC9f8BqaNi4x0GzFYAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((0,0),14,5.5,alpha=0.3))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because the run starts and ends with epsilon transitions, there's also a sub-run that covers the whole string but begins in state $q_2$ and ends in state $q_2$:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAZ7klEQVR4nO3df3RU9Z3/8ecbEkooAorR8isE1xS+gIAhWxGR31ql+KNf+C5F2nWt/QLHr2sptLtU6ynq4nF1d7UFlhC0Kq6iX0phQWsJYLDgaiRRxAgonkoX1t16upYK8kOg7/1jJhhCfkySuTOZT16Pc3IyM/fO5756b/PieufeO+buiIhIeNqlO4CIiERDBS8iEigVvIhIoFTwIiKBUsGLiAQqK90Bajr//PM9Pz8/krE/OXYi6WMe/exU0scUkfTK6dA+6WN26Zid9DGrVVZW/t7dc+ua1qoKPj8/n4qKikjG3rTrd0kfc8f+g0kfU0TSa1ifbkkfc+LAC5M+ZjUz+21903SIRkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUCp4EZFAqeBFRAKlghcRCZQKXkQkUK3qSlZpm55f/iC7yston5VN9555TJt7Pzmdu6Q7lkjG0x68pF1B4UjmLVvPvOJ15PbK56XnStIdSSQI2oOXlNq8spjKTWvpmtuDzl3PpVfBIMZOvfX09LwBQ3l724Y0JhQJh/bgJWUO7K1ix8svMGfJGm6+exH736s6a57tpavpXzQ6DelEwqM9eEmZD6oqGTzyKjp0zAFg4IhxZ0zfvLKYdu2zKBx/XTriiQRHBS+pZXW/XLFxDbvKy5j1wBOY1TOTiDRJpIdozGyfmb1tZjvMLJobvUvG6De4iKpXNnHi+DGOHTnM7vItAOyp2ErZqke5ZcHS03v3ItJyqdiDH+fuv0/BcqSV610wiGFjJvHwbTfS7cKe9Bs8HIC1S+7j5InPKLnz2wD0HTCUKXfck86oIkHQIRpJqQnTZzNh+mwASp9aBMD8x0vTGUkkWFEXvAOlZubAMnc/6wRnM5sJzATIy8uLOI6kw+Ky9+t8/eC+j7Hso1TVM73a7eMujiKWSPCiLvgr3P1DM7sA2Ghme9z91zVniJd+CUBRUZFHnEdakW6jZqQ7gkjQIv2Q1d0/jP/+CFgDfCXK5YmIyOciK3gz+6KZnVP9GLgaOPvKFhERiUSUh2guBNbEz2nOAp5x919FuDwREakhsoJ3998AQ6MaX0REGqZ70YiIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBCor3QEkszy//EF2lZfRPiub7j3zmDb3fnI6d0l3rLNkSs7WTusxs2kPXpqkoHAk85atZ17xOnJ75fPScyXpjlSnTMnZ2mk9ZjbtwUu9Nq8spnLTWrrm9qBz13PpVTCIsVNvPT09b8BQ3t62IY0JYzIlZ2un9Rge7cFLnQ7srWLHyy8wZ8kabr57Efvfqzprnu2lq+lfNDoN6T6XKTlbO63HMGkPXur0QVUlg0deRYeOOQAMHDHujOmbVxbTrn0WheOvS0e80zIlZ2un9RgmFbzUz+p+uWLjGnaVlzHrgScwq2emVMqUnK2d1mNwIj9EY2btzexNM3s+6mVJ8vQbXETVK5s4cfwYx44cZnf5FgD2VGylbNWj3LJg6em9vXTKlJytndZjmMzdo12A2VygCOji7pMbmreoqMgrKioiybFp1++SPuaO/QeTPmZrUv2hW7cLe9Lt/C9xQd6f8doLz3HyxGd06tINgL4DhjLljnsaHGdx2fstynH7uItTkrOt03qMGdanW9LHnDjwwqSPWc3MKt29qM5pURa8mfUGngQWAnNV8Jmr9KlFdMjpdMZZFYmKuuBraklO+VxbXo8hFXzUx+AfAf4GOKe+GcxsJjATIC8vL+I40pj6yvjgvo+x7KNUJVDWTSnk5mjoH4xEc0adMRNoPYYvsoI3s8nAR+5eaWZj65vP3UuAEojtwUeVR1qm26gZ6Y6QkEzJ2dppPYYhyg9ZrwCuN7N9wLPAeDP7lwiXJyIiNURW8O7+Q3fv7e75wDeAl9z9m1EtT0REzqQrWUVEApWSC53cfQuwJRXLEhGRGO3Bi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhKoRgvezP5PIq+JiEjrksge/A8TfE1ERFqRer/ww8yuBSYBvczspzUmdQFORh1MRERapqFvdPoQqACuByprvH4I+F6UoUREpOXqLXh3fwt4y8yecfcTKcwkIiJJkMh3sn7FzBYAfePzG+DuflGUwUREpGUSKfjHiB2SqQRORRtHRESSJZGC/6O7vxh5EhERSaqGzqIpjD8sM7OHgF8Ax6unu/sbEWcTEZEWaGgP/h9rPS+q8diB8cmPIyIiydLQWTTjUhlEovH88gfZVV5G+6xsuvfMY9rc+8np3CXdsTJOJqxHZZTaErlVwdw6fm41s2GpCCgtU1A4knnL1jOveB25vfJ56bmSdEfKSJmwHpVRakvkQ9ai+M/6+POvAduB2Wa2yt0fjCqcNM3mlcVUblpL19wedO56Lr0KBjF26q2np+cNGMrb2zakMWFmyIT1qIySiETuRdMdKHT3ee4+j1jZ5wKjgb+KMJs0wYG9Vex4+QXmLFnDzXcvYv97VWfNs710Nf2LRqchXebIhPWojJKoRPbg84DPajw/AfR196Nmdrye90iKfVBVyeCRV9GhYw4AA0ec+RHK5pXFtGufReH469IRL2NkwnpURklUIgX/DPCamf1r/Pl1wEoz+yKwK7Jk0nRW98sVG9ewq7yMWQ88gVk9M8nnMmE9KqMkoNFDNO5+H/B/gYPAH4HZ7n6vu3/q7jPqe5+ZdTSz183sLTN7x8zuSV5sqa3f4CKqXtnEiePHOHbkMLvLtwCwp2IrZase5ZYFS0/vTUn9MmE9KqMkqqELnbq4+ydmdh7wQfynetp57v5xI2MfB8a7+2Ezywa2mdmL7v5aUpLLGXoXDGLYmEk8fNuNdLuwJ/0GDwdg7ZL7OHniM0ru/DYAfQcMZcod+re2PpmwHpVREtXQIZpngMnE7kHjxG8yVuN3gzcbc3cHDsefZsd/vIV5pQETps9mwvTZAJQ+tQiA+Y+XpjNSRsqE9aiMkoiGLnSaHP/dr7mDm1l7Yv9AXAwscffyOuaZCcwEyMvLa+6i2qTFZe/XO+3gvo+x7KNUNTAPwO3jLk52rIxU37psTetRGaWpGv2Q1WKfgswA+rn7fWaWB3zJ3V9v7L3ufgoYZmbdgDVmNtjdq2rNUwKUABQVFWkPP0m6jar34xFpgkxYj8oo9UnkPPh/Bi4Hboo/PwQsacpC3P0gsAW4pinvExGR5kuk4C9z9/8HHANw9z8AHRp7k5nlxvfcMbMcYCKwpwVZRUSkCRI5D/5E/Fi6Q6y4gT8l8L4ewJPx97YD/r+7P9/spCIi0iSJFPxPgTXABWa2EJgK/KixN7n7TuDSlsUTEZHmarTg3f1pM6sEJhA7RfJGd98deTIREWmRRPbgAfYCn1TPb2Z57v7vkaUSEZEWS+Q0yb8Gfgz8jtiXbldf6DQk2mgiItISiezBfxfo7+7/HXUYERFJnkROk9xP7CZjIiKSQRq62djc+MPfAFvM7AViNxADwN3/KeJsIiLSAg0dojkn/vvf4z8dSOACJxERaR0autmY7uEpIpLBEjkGLyIiGUgFLyISqEYLPv6NTrVfa/Y94kVEJDUS2YNfb2Zdqp+Y2UBgfXSRREQkGRIp+PuJlXxnMxsOrAK+GW0sERFpqURuNvZC/EuzS4mdOnmju++NPJmIiLRIQxc6LeLML8nuQuyip782M9z9jqjDiYhI8zW0B19R63lllEFERCS5GrrQ6UkAM/sicCz+BdrEv6HpC6mJJyIizZXIh6ybgZwaz3OATdHEERGRZEmk4Du6++HqJ/HHnaKLJCIiyZBIwX9qZoXVT+KnSh6NLpKIiCRDIl/4MQdYZWYfxp/3AKZFF0lERJIhkfPgt5vZAKA/sa/r2+PuJyJPJiIiLZLol273BwYCHYFL4+fBr4guloiItFQiX7r9Y2AssYL/JXAtsA1QwYuItGKJfMg6FZgA/Je73wIMRefBi4i0eokcojnq7n8ys5Pxu0p+BFwUca426fnlD7KrvIz2Wdl075nHtLn3k9O5S+NvlIyk7Z0cWo/1S2QPvsLMugHLid2u4A3g9UhTtVEFhSOZt2w984rXkdsrn5eeK0l3JImQtndyaD3WL5GzaG6LPyw2s18BXdx9Z7Sxwrd5ZTGVm9bSNbcHnbueS6+CQYydeuvp6XkDhvL2tg1pTCjJpO2dHFqPTZPINzptrn7s7vvcfWfN16TpDuytYsfLLzBnyRpuvnsR+9+rOmue7aWr6V80Og3pJNm0vZND67HpGrpdcEdityQ438zOJXYOPMRuG9wzBdmC9UFVJYNHXkWHjrFb/AwcMe6M6ZtXFtOufRaF469LRzxJMm3v5NB6bLqGDtHMInYVa09ix96rC/4TYEnEucJndb9csXENu8rLmPXAE5jVM5NkHm3v5NB6bJJ6D9G4+0/cvR/wfXe/yN37xX+GuvvixgY2sz5mVmZmu83sHTP7blKTZ7B+g4uoemUTJ44f49iRw+wu3wLAnoqtlK16lFsWLD29lyKZT9s7ObQemy6R0yT/y8zOcfdDZvYjoBD4O3d/o5H3nQTmufsbZnYOUGlmG919V0tDZ7reBYMYNmYSD992I90u7Em/wcMBWLvkPk6e+IySO78NQN8BQ5lyxz3pjCpJoO2dHFqPTZdIwd/t7qvMbBTwVeAfgKXAZQ29yd3/E/jP+ONDZrYb6AW0+YIHmDB9NhOmzwag9KlFAMx/vDSdkSRC2t7JofXYNIkU/Kn4768BS939X81sQVMWYmb5wKVAeR3TZgIzAfLy8poybMZZXPZ+na8f3Pcxln2UqnqmV7t93MVRxJII1LetQdu7qfR303yJFPx/mNkyYCLw92b2BRK7QAoAM+sMrAbmuPsntae7ewlQAlBUVOS1p7cF3UbNSHcESSFt7+TQemxcIkX9F8AG4Bp3PwicB/wgkcHNLJtYuT/t7r9odkoREWmyRK5kPQL8osbz08fWG2Kxc5UeA3a7+z+1JKSIiDRdwodamuEK4FvAeDPbEf+ZFOHyRESkhkS/8KPJ3H0b9V6WICIiUYtyD15ERNJIBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBykp3gEz2/PIH2VVeRvusbLr3zGPa3PvJ6dwl3bFEpAVK/uEeXtuykazsbHr2yef7f/cInbt0TXesZtEefAsUFI5k3rL1zCteR26vfF56riTdkUSkhQovH8PytVsoWVNGr74XsXL5T9Mdqdm0B5+gp5c9wqZ1q8j9Uk+6ntudLw8aQv+JN52enjdgKG9v25DGhCLSVJtXFlO5aS1dc3vQueu59CoYxJzvzTs9/X8NHc7W0ufTmLBlVPAJeO+dt9jy4lqW/nwjp06d4rapV/HlQUPOmGd76WqGjp6UpoQi0lQH9lax4+UXmLNkDX86dYpHbv/f9CoYdMY8G36xkjHX3pCmhC2ngk9AVWU5V0y4lo45nQC4fNxXz5i+eWUx7dpnUTj+unTEE5Fm+KCqksEjr6JDxxwABo4Yd8b0p5c9QvusLCZMnpKOeEmhgk+QmdX5esXGNewqL2PWA0/UO4+ItFL1/MmWrn2O8pc38uBjqzL67zqyD1nN7Gdm9pGZVUW1jFS5pGgEr2x+kePHjnLk08O8uqUUgD0VWylb9Si3LFh6ei9ARDJDv8FFVL2yiRPHj3HsyGF2l28BYPvWl3juscXcu/jJ0//Vnqmi3IN/AlgMrIhwGSlRMHAIY665gdlTJnJBz95cMvwyANYuuY+TJz6j5M5vA9B3wFCm3HFPOqOKSIJ6Fwxi2JhJPHzbjXS7sCf9Bg8HYPHCOzlx4jP+9jvTgNgHrXN+/GA6ozZbZAXv7r82s/yoxk+1GbPmMGPWHABWLHkIgPmPl6Yzkoi00ITps5kwfTYApU8tAuDJX72WzkhJlfZj8GY2E5gJkJeXl+Y0n/vOiop6px1860MsO4eu7d9vcIxH/7IoqZmG9emW1PEyZUxlbJ3jRTFmKjLW97d9cN/HWPZRqhr426+W7L/tqKS94N29BCgBKCoq8jTHSUi3UTPSHUFEkizEv2tdySoiEigVvIhIoKI8TXIl8CrQ38wOmNmtUS1LRETOFuVZNNOjGltERBqnQzQiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFqMwX/8oZ1fOf60Vw9uAfvVu1IdxwRaUPuvvtuhgwZwrBhw7j66qv58MMPU7LcNlPw+RcP4Mc/+RmXFI1IdxQRaWN+8IMfsHPnTnbs2MHkyZO59957U7LcrJQsJcUWLlzIihUr6NOnD7m5uQwfPpxhk76V7lgi0gY8vewRNq1bRe6XetL13O58edAQJj50z+npn376KWaWkizBFXxlZSXPPvssb775JidPnqSwsJDhw4enO5aItAHvvfMWW15cy9Kfb+TUqVPcNvUqvjxoCAB33XUXK1asoGvXrpSVlaUkT3CHaLZu3crXv/51OnXqRJcuXbj++uvTHUlE2oiqynKumHAtHXM68cXO53D5uK+enrZw4UL279/PjBkzWLx4cUryBFfwQMr+80dEpLbG+uemm25i9erVKckSacGb2TVm9q6ZvW9m86NcVrXRo0ezZs0ajh49yqFDh1i/fn0qFisiwiVFI3hl84scP3aUI58e5tUtpQDs3bv39Dzr1q1jwIABKckT2TF4M2sPLAGuAg4A281snbvvimqZAIWFhUybNo1hw4bRt29frrzySgC2bfolS+6/iz9+/N/86LZv8mf9B/PA8mejjCIibUzBwCGMueYGZk+ZyAU9e3PJ8MsAmD9/Pu+++y7t2rWjb9++FBcXpyRPlB+yfgV4391/A2BmzwI3AJEWPMQ+zLjrrrsAWLBgAQCjJk5i1MRJUS9aRNq4GbPmMGPWHABWLHkIIGWHZGozd49mYLOpwDXu/p34828Bl7n77bXmmwnMjD/tD7yb5Cg9gVPA7xKc/3zg90nOkOwxMyFjFGMqY+scL1PGTEfGpvZPc/R199y6JkS5B1/XJw1n/Wvi7iVASYQ5msTMKty9qDWPmQkZoxhTGVvneJkyZiZkTLYoP2Q9APSp8bw3kJrrc0VEJNKC3w4UmFk/M+sAfANYF+HyRESkhsgO0bj7STO7HdgAtAd+5u7vRLW8JIricFGyx8yEjFGMqYytc7xMGTMTMiZVZB+yiohIegV5JauIiKjgRUSCpYKXVs/M8s2sqrWOF9WYmUDbpnVTwYuIBEoFHyEzW2tmlWb2TvyK3TYxZhQZgSwze9LMdprZz82sUysbL+ljZsK2jmtz2yZjuLt+IvoBzov/zgGqgO5tYcwIxssndhX0FfHnPwO+31rGi3DMTNjWbXLbZMqP9uCjdYeZvQW8Ruyq3oI2MmYUGfe7+yvxx/8CjGpl40UxZiZsa2ib2yYjBPeVfa2FmY0FJgKXu/sRM9sCdAx9zCgyxtW+YKOlF3Ake7ykjpkJ27qGNrVtMon24KPTFfhD/A9pADCijYwZRUaAPDO7PP54OrCtlY2X7DEzYVtXa2vbJmOo4KPzK2If7OwE7iP2n8RtYcwoMgLsBm6Oj3sesLSVjZfsMTNhW1dra9smY+hWBSIigdIevIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwkpHM7N8iGDPfzG5q4nvubGT6L82sW8uSiTSPTpMUiYtf6fl9d5/chPccdvfOdbxuxP6+/pTEiCJNoj14yUhmdjj+e6yZbYnfIXCPmT0dL1fMbJ+Z/b2ZvR7/uTj++hNmNrX2WMADwJVmtsPMvldreT3M7NfxaVVmdqWZPQDkxF97Ov5fALvN7J+BN4A+8Qzn15i2PH4nx1Izy4mP/efxuxy+amYPWRu9d7kknwpeQnApMAcYCFwEXFFj2ifu/hVgMfBII+PMB7a6+zB3f7jWtJuADe4+DBgK7HD3+cDR+Pwz4vP1B1a4+6Xu/ttaYxQAS9x9EHAQmBJ//XFgtrtfDpxK8H+zSKNU8BKC1939QPxwyA5it4ettrLG78trv7EJtgO3mNkC4BJ3P1TPfL919/puAfCBu++IP64E8uPH589x9+rPFJ5pQUaRM6jgJQTHazw+xZl3SfU6Hp8k/v/9+OGcDo0twN1/DYwG/gN4ysz+sp5ZP21iTmts2SLNpYKX0E2r8fvV+ON9wPD44xuA7PjjQ8A5dQ1iZn2Bj9x9OfAYUBifdMLMsut6TyLc/Q/AITOrvrPjN5o7lkhtKngJ3RfMrBz4LlD9welyYIyZvQ5cxud73TuBk2b2Vu0PWYGxwA4ze5PYsfOfxF8vAXaa2dMtyHgrUGJmrxLbo/9jC8YSOU2nSUqwzGwfUOTuv093loaYWWd3rz4raD7Qw92/m+ZYEgB9o5NI+n3NzH5I7O/xt8BfpTeOhEJ78CIigdIxeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQP0Pv0aOQNwXge0AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((0,0),14,5.5,alpha=0.3))\n", "ax.add_patch(patches.Rectangle((1,1),12,4.5,alpha=0.3))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we should add a rule $A_{q_1q_3} \\rightarrow A_{q_2q_2}$. The next smallest sub-run is the one that covers the whole string except the first and last symbols. It, too, begins in state $q_2$ and ends in state $q_2$:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAat0lEQVR4nO3de3RV9Z338fcXEkooQrxEK0gSrAgFlJhkKt5QRFoveGHp81BlOo61D7IctVR0hsq4RC3WS5+prTCG4A0cRR/UMICjBDBY9NFIoogRvK1KB8eZWsdSQQGBfuePc4Ih5HKSnH0uv3xea2XlnLP3+e1P924+bvbZex9zd0REJDw90h1ARESioYIXEQmUCl5EJFAqeBGRQKngRUQClZPuAE0ddthhXlxcnO4YCft85+6kjrfjq71JHU+kO8jr1TOp4/XrnZvU8aJWX1//qbsXtDQtowq+uLiYurq6dMdI2KqNf0jqeOu3bE3qeCLdQcmg/KSOd9bwI5I6XtTM7PetTdMhGhGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQGXUlazSPS2ffzcba2vomZPLoQMKmXT9HeT17ZfuWCJZT3vwknZDSk9m+rxlTK9YSsHAYl54sjLdkUSCoD14SanViyqoX7WE/gVH0rf/wQwcMoIzLrly3/TCYaN466UVaUwoEg7twUvKfPR+A+tffJZpc6u4/Ob72PJewwHzrKt+mqHlY9KQTiQ82oOXlPmwoZ6RJ4+nV+88AIaPHrvf9NWLKujRM4fSM89PRzyR4KjgJbWs5ZfrVlaxsbaGq+58BLNWZhKRDon0EI2ZbTazt8xsvZllz43eJRKDR5bT8PIqdu/ayc4vt7Opdg0A79StpWbxA1wx6/59e/ci0nWp2IMf6+6fpmA5kuGOGjKCktPP5VdXX0T+EQMYPLIMgCVzb2fP7q+ovOlHABQNG8XF192azqgiQdAhGkmpcZdOZdylUwGofvQ+AGY8XJ3OSCLBirrgHag2MwfmufsBJzib2RRgCkBhYWHEcSQd5tR80OLrWzd/huXuoKGV6Y2uGXtMFLFEghd1wZ/i7h+b2eHASjN7x91/23SGeOlXApSXl3vEeSSD5J86Od0RRIIW6Yes7v5x/PcnQBXw3SiXJyIiX4us4M3sm2Z2UONj4HvAgVe2iIhIJKI8RHMEUBU/pzkHeNzdn49weSIi0kRkBe/uvwNGRTW+iIi0TfeiEREJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJVE66A0h2WT7/bjbW1tAzJ5dDBxQy6fo7yOvbL92xDpAtOTOd1mN20x68dMiQ0pOZPm8Z0yuWUjCwmBeerEx3pBZlS85Mp/WY3bQHL61avaiC+lVL6F9wJH37H8zAISM445Ir900vHDaKt15akcaEMdmSM9NpPYZHe/DSoo/eb2D9i88ybW4Vl998H1veazhgnnXVTzO0fEwa0n0tW3JmOq3HMGkPXlr0YUM9I08eT6/eeQAMHz12v+mrF1XQo2cOpWeen454+2RLzkyn9RgmFby0zlp+uW5lFRtra7jqzkcwa2WmVMqWnJlO6zE4kR+iMbOeZvaGmS2PelmSPINHltPw8ip279rJzi+3s6l2DQDv1K2lZvEDXDHr/n17e+mULTkzndZjmMzdo12A2fVAOdDP3Se0NW95ebnX1dVFmieZVm38Q1LHW79la1LH66rGD93yjxhA/mHf4vDCb/Pqs0+yZ/dX9OmXD0DRsFFcfN2tbY4zp+aDLuW4ZuwxKcnZ3WXreiwZlJ/U8c4afkRSx4uamdW7e3mL06IseDM7ClgAzAauV8G3LdMKvqnqR++jV16f/c6qSFTUBd9UV3LK17JpPargWy/4qI/B3wv8PXBQazOY2RRgCkBhYWHEcaQ9rZXx1s2fYbk7aEigrDtSyJ3R1n8wEs0ZdcZsoPUYvsgK3swmAJ+4e72ZndHafO5eCVRCbA8+qjzSNfmnTk53hIRkS85Mp/UYhig/ZD0FuMDMNgNPAGea2b9EuDwREWkisoJ395+5+1HuXgz8AHjB3f86quWJiMj+dCWriEigUnKhk7uvAdakYlkiIhKjPXgRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAtVuwZvZ/0rkNRERySyJ7MH/LMHXREQkg7T6hR9mdg5wLjDQzH7TZFI/YE/UwUREpGva+kanj4E64AKgvsnr24CfRhlKRES6rtWCd/c3gTfN7HF3353CTCIikgSJfCfrd81sFlAUn98Ad/ejowwmIiJdk0jBP0jskEw9sDfaOCIikiyJFPyf3f25yJOIiEhStXUWTWn8YY2Z3QM8A+xqnO7ur0ecTUREuqCtPfj/2+x5eZPHDpyZ/DgiIpIsbZ1FMzaVQSQay+ffzcbaGnrm5HLogEImXX8HeX37pTtW1smG9aiM0lwityq4voWfK82sJBUBpWuGlJ7M9HnLmF6xlIKBxbzwZGW6I2WlbFiPyijNJfIha3n8Z1n8+XnAOmCqmS1297ujCicds3pRBfWrltC/4Ej69j+YgUNGcMYlV+6bXjhsFG+9tCKNCbNDNqxHZZREJHIvmkOBUnef7u7TiZV9ATAG+NsIs0kHfPR+A+tffJZpc6u4/Ob72PJewwHzrKt+mqHlY9KQLntkw3pURklUInvwhcBXTZ7vBorcfYeZ7WrlPZJiHzbUM/Lk8fTqnQfA8NH7f4SyelEFPXrmUHrm+emIlzWyYT0qoyQqkYJ/HHjVzP41/vx8YJGZfRPYGFky6Thr+eW6lVVsrK3hqjsfwayVmeRr2bAelVES0O4hGne/Hfg/wFbgz8BUd7/N3b9w98mtvc/MepvZa2b2ppm9bWa3Ji+2NDd4ZDkNL69i966d7PxyO5tq1wDwTt1aahY/wBWz7t+3NyWty4b1qIySqLYudOrn7p+b2SHAh/GfxmmHuPtn7Yy9CzjT3bebWS7wkpk95+6vJiW57OeoISMoOf1cfnX1ReQfMYDBI8sAWDL3dvbs/orKm34EQNGwUVx8nf5b25psWI/KKIlq6xDN48AEYvegceI3GWvyu82bjbm7A9vjT3PjP97FvNKGcZdOZdylUwGofvQ+AGY8XJ3OSFkpG9ajMkoi2rrQaUL89+DODm5mPYn9B+IYYK6717YwzxRgCkBhYWFnF9Utzan5oNVpWzd/huXuoKGNeQCuGXtMsmNlpdbWZSatR2WUjmr3Q1aLfQoyGRjs7rebWSHwLXd/rb33uvteoMTM8oEqMxvp7g3N5qkEKgHKy8u1h58k+ae2+vGIdEA2rEdllNYkch78PwMnAZfFn28D5nZkIe6+FVgDnN2R94mISOclUvAnuvvfATsB3P1PQK/23mRmBfE9d8wsDzgLeKcLWUVEpAMSOQ9+d/xYukOsuIG/JPC+I4EF8ff2AP6fuy/vdFIREemQRAr+N0AVcLiZzQYuAf6xvTe5+wbghK7FExGRzmq34N39MTOrB8YRO0XyInffFHkyERHpkkT24AHeBz5vnN/MCt393yNLJSIiXZbIaZLXArcAfyD2pduNFzodH200ERHpikT24H8CDHX3/446jIiIJE8ip0luIXaTMRERySJt3Wzs+vjD3wFrzOxZYjcQA8Dd/ynibCIi0gVtHaI5KP773+M/vUjgAicREckMbd1sTPfwFBHJYokcgxcRkSykghcRCVS7BR//Rqfmr3X6HvEiIpIaiezBLzOzfo1PzGw4sCy6SCIikgyJFPwdxEq+r5mVAYuBv442loiIdFUiNxt7Nv6l2dXETp28yN3fjzyZiIh0SVsXOt3H/l+S3Y/YRU/Xmhnufl3U4UREpPPa2oOva/a8PsogIiKSXG1d6LQAwMy+CeyMf4E28W9o+kZq4omISGcl8iHraiCvyfM8YFU0cUREJFkSKfje7r698Un8cZ/oIomISDIkUvBfmFlp45P4qZI7ooskIiLJkMgXfkwDFpvZx/HnRwKTooskIiLJkMh58OvMbBgwlNjX9b3j7rsjTyYiIl2S6JduDwWGA72BE+LnwS+MLpaIiHRVIl+6fQtwBrGC/zfgHOAlQAUvIpLBEvmQ9RJgHPBf7n4FMAqdBy8ikvESOUSzw93/YmZ74neV/AQ4OuJc3dLy+XezsbaGnjm5HDqgkEnX30Fe337tv1GykrZ3clT+8lZeXbOSnNxcBgwq5oaf30vffv3THSsjJLIHX2dm+cB8YrcreB14LdJU3dSQ0pOZPm8Z0yuWUjCwmBeerEx3JImQtndylJ50OvOXrKGyqoaBRUezaP5v0h0pYyRyFs3V8YcVZvY80M/dN0QbK3yPzbuXVUsXU/CtAfQ/+FCOHXE8Q8+6bN/0wmGjeOulFWlMKMm0elEF9auW0L/gSPr2P5iBQ0ZwxiVX7puu7Z2YltbjtJ9O3zf9O6PKWFu9PI0JM0si3+i0uvGxu2929w1NX5OOe+/tN1nz3BLuf2olt/z6Id5rWH/APOuqn2Zo+Zg0pJNk++j9Bta/+CzT5lZx+c33seW9hgPm0fZuXyLrccUzi/ir085MQ7rM1NbtgnsTuyXBYWZ2MLFz4CF22+ABKcgWrIb6Wk4Zdw6982J3fDhp7Pf3m756UQU9euZQeub56YgnSfZhQz0jTx5Pr96xWzoNHz12v+na3olpbz0+Nu9eeubkMG7CxemIl5HaOkRzFbGrWAcQO/beWPCfA3MjzhU8M2vx9bqVVWysreGqOx9pdR7JQq1sSm3vDmplFVUveZLaF1dy94OLtR6baPUQjbv/2t0HAze4+9HuPjj+M8rd57Q3sJkNMrMaM9tkZm+b2U+SmjyLHVc+mpdXP8eunTv48ovtvLKmGoB36tZSs/gBrph1/769FMl+g0eW0/DyKnbv2snOL7ezqXYNoO3dUa2tx3VrX+DJB+dw25wF+/5VLDGJnCb5X2Z2kLtvM7N/BEqBn7v76+28bw8w3d1fN7ODgHozW+nuG7saOtsNGX48p599IVMvPovDBxzFcWUnArBk7u3s2f0VlTf9CICiYaO4+Lpb0xlVkuCoISMoOf1cfnX1ReQfMYDBI8sAbe+Oam09zpl9E7t3f8U//Dh2i6zvjCpj2i13pzNqxkik4G9298VmdirwfeCXwP3AiW29yd3/E/jP+ONtZrYJGAh0+4IHmHzVNCZfNQ2AhXPvAWDGw9XpjCQRGnfpVMZdOhWA6kfvA7S9O6Ol9bjg+VfTGSmjJVLwe+O/zwPud/d/NbNZHVmImRUDJwC1LUybAkwBKCws7MiwWefHC5t/C2LM1jc/xnLz6N/zgzbf/8DflCc9U8mg/IwfMxsztratAbZu/gzL3UFDTWq3dzauR2jj76ZxPbaxriGav5tskUjB/4eZzQPOAu4ys2+Q2AVSAJhZX+BpYJq7f958urtXApUA5eXl3nx6d5B/6uR0R5AU0vZODq3H9iVS1P8bWAGc7e5bgUOAGxMZ3MxyiZX7Y+7+TKdTiohIhyVyJeuXwDNNnu87tt4Wi52r9CCwyd3/qSshRUSk4xI+1NIJpwA/BM40s/Xxn3MjXJ6IiDSR6Bd+dJi7v0SrlyWIiEjUotyDFxGRNFLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKBy0h0gm1X+8lZeXbOSnNxcBgwq5oaf30vffv3THUtEuuDGG29k2bJl9OrVi29/+9s8/PDD5OfnpztWp2gPvgtKTzqd+UvWUFlVw8Cio1k0/zfpjiQiXTR+/HgaGhrYsGEDxx57LL/4xS/SHanTtAefoNmzZ7Nw4UIGDRpEQUEBZWVllJ/7w33TvzOqjLXVy9OYUEQ66rF597Jq6WIKvjWA/gcfyrEjjmfePbfumz569GieeuqpNCbsGhV8Aurr63niiSd444032LNnD6WlpZSVle03z4pnFnH6ORemKaGIdNR7b7/JmueWcP9TK9m7dy9XXzKeY0ccv988Dz30EJMmTUpTwq5TwSdg7dq1TJw4kT59+gBwwQUX7Df9sXn30jMnh3ETLk5HPBHphIb6Wk4Zdw6982J/1yeN/f5+02fPnk1OTg6TJ09OR7ykUMEnyMxafL16yZPUvriSux9c3Oo8IpKZWvubXbBgAcuXL2f16tVZ/Xcd2YesZvaQmX1iZg1RLSNVxowZQ1VVFTt27GDbtm0sW7YMgHVrX+DJB+dw25wF+/YCRCQ7HFc+mpdXP8eunTv48ovtvLKmGoDnn3+eu+66i6VLl+77V3u2inIP/hFgDrAwwmWkRGlpKZMmTaKkpISioiJOO+00AObMvondu7/iH34cO0b3nVFlTLvl7nRGFZEEDRl+PKeffSFTLz6LwwccxXFlJwJwzTXXsGvXLsaPHw/EPmitqKhIZ9ROi6zg3f23ZlYc1fipNnPmTGbOnAnArFmzAFjw/KtpTCQiXTX5qmlMvmoaAAvn3gPABx98kM5ISZX2Y/BmNgWYAlBYWJjmNF8rnvFsq9O2vvQelptH/0/r2hxj853nJTXTWcOPSOp42TKmMmbmeFGMmYqMrf1tb33zYyw3jxVt/O03SvbfdlTSXvDuXglUApSXl3ua4yQk/9Ts/VRdRFoW4t+1rmQVEQmUCl5EJFBRnia5CHgFGGpmH5nZlVEtS0REDhTlWTSXRjW2iIi0T4doREQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQCpYIXEQmUCl5EJFAqeBGRQKngRUQC1W0KfvHixYwYMYIePXpQV1eX7jgi0o3cfPPNHH/88ZSUlPC9732Pjz/+OCXL7TYFP3LkSJ555hnGjBmT7igi0s3ceOONbNiwgfXr1zNhwgRuu+22lCw3JyVLSbHZs2ezcOFCBg0aREFBAWVlZdxwww3pjiUi3UB7/fPFF19gZinJElzB19fX88QTT/DGG2+wZ88eSktLKSsrS3csEekG2uqfmTNnsnDhQvr3709NTU1K8gR3iGbt2rVMnDiRPn360K9fPy644IJ0RxKRbqKt/pk9ezZbtmxh8uTJzJkzJyV5git4IGX//BERaa69/rnssst4+umnU5Il0oI3s7PN7F0z+8DMZkS5rEZjxoyhqqqKHTt2sG3bNpYtW5aKxYqItNo/77///r55li5dyrBhw1KSJ7Jj8GbWE5gLjAc+AtaZ2VJ33xjVMgFKS0uZNGkSJSUlFBUVcdpppwFQVVXFtddeyx//+EfOO+88SkpKWLFiRZRRRKSbaa1/ZsyYwbvvvkuPHj0oKiqioqIiJXmi/JD1u8AH7v47ADN7ArgQiLTgIfZhxsyZMwGYNWsWABMnTmTixIlRL1pEurmW+idVh2SaM3ePZmCzS4Cz3f3H8ec/BE5092uazTcFmBJ/OhR4N8lRBgB7gT8kOP9hwKdJzpDsMbMhYxRjKmNmjpctY6YjY0f7pzOK3L2gpQlR7sG39EnDAf81cfdKoDLCHB1iZnXuXp7JY2ZDxijGVMbMHC9bxsyGjMkW5YesHwGDmjw/CkjN9bkiIhJpwa8DhpjZYDPrBfwAWBrh8kREpInIDtG4+x4zuwZYAfQEHnL3t6NaXhJFcbgo2WNmQ8YoxlTGzBwvW8bMhoxJFdmHrCIikl5BXskqIiIqeBGRYKngJeOZWbGZNWTqeFGNmQ20bTKbCl5EJFAq+AiZ2RIzqzezt+NX7HaLMaPICOSY2QIz22BmT5lZnwwbL+ljZsO2jut22yZruLt+IvoBDon/zgMagEO7w5gRjFdM7CroU+LPHwJuyJTxIhwzG7Z1t9w22fKjPfhoXWdmbwKvEruqd0g3GTOKjFvc/eX4438BTs2w8aIYMxu2NXTPbZMVgvvKvkxhZmcAZwEnufuXZrYG6B36mFFkjGt+wUZXL+BI9nhJHTMbtnUT3WrbZBPtwUenP/Cn+B/SMGB0NxkziowAhWZ2UvzxpcBLGTZessfMhm3dqLttm6yhgo/O88Q+2NkA3E7sn8TdYcwoMgJsAi6Pj3sIcH+GjZfsMbNhWzfqbtsma+hWBSIigdIevIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwkpXM7P9HMGaxmV3Wwffc1M70fzOz/K4lE+kcnSYpEhe/0vMGd5/Qgfdsd/e+LbxuxP6+/pLEiCIdoj14yUpmtj3++wwzWxO/Q+A7ZvZYvFwxs81mdpeZvRb/OSb++iNmdknzsYA7gdPMbL2Z/bTZ8o40s9/GpzWY2WlmdieQF3/tsfi/ADaZ2T8DrwOD4hkOazJtfvxOjtVmlhcf+6/idzl8xczusW5673JJPhW8hOAEYBowHDgaOKXJtM/d/bvAHODedsaZAax19xJ3/1WzaZcBK9y9BBgFrHf3GcCO+PyT4/MNBRa6+wnu/vtmYwwB5rr7CGArcHH89YeBqe5+ErA3wf/NIu1SwUsIXnP3j+KHQ9YTuz1so0VNfp/U/I0dsA64wsxmAce5+7ZW5vu9u7d2C4AP3X19/HE9UBw/Pn+Quzd+pvB4FzKK7EcFLyHY1eTxXva/S6q38HgP8f/vxw/n9GpvAe7+W2AM8B/Ao2b2N63M+kUHc1p7yxbpLBW8hG5Sk9+vxB9vBsrijy8EcuOPtwEHtTSImRUBn7j7fOBBoDQ+abeZ5bb0nkS4+5+AbWbWeGfHH3R2LJHmVPASum+YWS3wE6Dxg9P5wOlm9hpwIl/vdW8A9pjZm80/ZAXOANab2RvEjp3/Ov56JbDBzB7rQsYrgUoze4XYHv2fuzCWyD46TVKCZWabgXJ3/zTdWdpiZn3dvfGsoBnAke7+kzTHkgDoG51E0u88M/sZsb/H3wN/m944EgrtwYuIBErH4EVEAqWCFxEJlApeRCRQKngRkUCp4EVEAvU/H1eR/ICHpC0AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((1,1),12,4.5,alpha=0.3))\n", "ax.add_patch(patches.Rectangle((2,2),10,3.5,alpha=0.3))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we should add a rule $A_{q_2q_2} \\rightarrow \\texttt{a} A_{q_2q_2} \\texttt{b}$. Now what is the next smallest sub-run? Notice that if we lop off the first and last symbols again, the result wouldn't be a sub-run:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXhU9dn/8fcNiRB2WYxsSQBFRMEQYoUiWFSsCgW5rFKh2gUftIpKVSzKr1epLQ8grUUFBSxY8MENldUKKgXBHQKIKIqCWBWKUkUjIBC5f39kwABZJmROZubk87quuTJzlu/5cA7nzjdnG3N3REQkfKrFO4CIiARDBV5EJKRU4EVEQkoFXkQkpFTgRURCKiXeAYpq3LixZ2VlxTtG3Hz97f6Yt7lzd+zbFDlWDWqlxrzNejVj32YyycvL2+HuTYobl1AFPisri1WrVsU7Rty88M72mLc5b+2nMW9T5Fj1y24e8zbPb58e8zaTiZl9VNI4HaIREQkpFXgRkZBSgRcRCSkVeBGRkFKBFxEJKRV4EZGQUoEXEQkpFXgRkZBSgRcRCamEupNVqqaXH5nAh6uXUz0llfrpLThvyChq1K4b71giSU89eIm7lqefxcBxT3DF2MdpcGImefMfinckkVBQD14q1aq503j3pWeo0zCdtHrH06RVO3J6X3VofPpJp7PpjSVxTCgSHurBS6X57MMNbHx1MQNGz+LiYeP5bPPbR02z4cX5ZJ7RLQ7pRMJHPXipNFvfXUObM3uSWiMNgKyccw4bv2ruNKpVr07bbhfFI55I6KgHL5XMih26YfkCPlyzgl7X/Rmz4qcRkfIJtMCb2RYze8vM1ppZ1X3QuwDQrF0nNq9aSsG+b9m3ZxdbVi8H4KM3X2H1ghn0ueVvh3r3IlJxlXGIpqe776iE5UiCO6HVqZzc5QIeu2MgdRudSLN2nQBYPmMc3+3fz7wx1wGQflIHeg6+I55RRUJBx+ClUuVeMpjcSwYD8PpTUwC48u558YwkElpBF3gHnjMzB6a4+9QjJzCzIcAQgIyMjIDjSDwsWLet2OE7t+djqQV8WsL4g37SsWkQsURCL+gC383dt5rZCcDzZvauuy8vOkGk6E8FyM3N9YDzSAJpcPageEcQCbVAT7K6+9bIz8+AOcAPglyeiIh8L7ACb2a1zazuwffABcD6oJYnIiKHC/IQTTowJ3JNcwrwiLsvCnB5IiJSRGAF3t03A2cE1b6IiJROd7KKiISUCryISEipwIuIhJQKvIhISKnAi4iElAq8iEhIqcCLiISUCryISEipwIuIhJQKvIhISKnAi4iElAq8iEhIqcCLiISUCryISEipwIuIhJQKvIhISKnAi4iElAq8iEhIqcCLiISUCryISEipwIuIhJQKvIhISKnAi4iElAq8iEhIqcCLiIRUSrwDSHJ5+ZEJfLh6OdVTUqmf3oLzhoyiRu268Y51lGTJmei0HpObevBSLi1PP4uB457girGP0+DETPLmPxTvSMVKlpyJTusxuakHLyVaNXca7770DHUappNW73iatGpHTu+rDo1PP+l0Nr2xJI4JCyVLzkSn9Rg+6sFLsT77cAMbX13MgNGzuHjYeD7b/PZR02x4cT6ZZ3SLQ7rvJUvORKf1GE7qwUuxtr67hjZn9iS1RhoAWTnnHDZ+1dxpVKtenbbdLopHvEOSJWei03oMJ/XgpRRW7NANyxfw4ZoV9Lruz5gVP03lSpaciU7rMWwCL/BmVt3M1pjZwqCXJbHTrF0nNq9aSsG+b9m3ZxdbVi8H4KM3X2H1ghn0ueVvh3p78ZQsOROd1mM4mbsHuwCzm4FcoJ679ylt2tzcXF+1alWgeRLZC+9sj3mb89Z+eszzHjzpVrfRidRplM7xzVvx9pKn+G7/fmrWqQ9A+kkd6Dn4jlLbWbBu2zFnAPhJx6aVkrOqq4z12C+7eaziHnJ++/SYt5lMzCzP3XOLHRdkgTezFsAMYDRwswp86RKtwBf1+lNTSK2ZdthVFdEKusAXVZGc8r2g1qMKfOyVVuCDPsk6AbgNKPHOCDMbAgwByMjICDiOlKWkYrxzez6WWsCnURTr8hTkY1HaL4xocwadMRloPYZfYAXezPoAn7l7npn9qKTp3H0qMBUKe/BB5ZGKaXD2oHhHiEqy5Ex0Wo/hEORJ1m5AXzPbAjwGnGtm/xfg8kREpIjACry73+7uLdw9C/gZ8C93/3lQyxMRkcPpOngRkZCqlDtZ3X0ZsKwyliUiIoXUgxcRCSkVeBGRkFKBFxEJKRV4EZGQUoEXEQkpFXgRkZBSgRcRCSkVeBGRkFKBFxEJKRV4EZGQUoEXEQkpFXgRkZBSgRcRCSkVeBGRkCqzwJvZZdEMExGRxBJND/72KIeJiEgCKfELP8zsIuBioLmZ3VtkVD2gIOhgIiJSMaV9o9NWYBXQF8grMjwf+G2QoUREpOJKLPDu/ibwppk94u77KzGTiIjEQDTfyfoDMxsFZEamN8DdvXWQwUREpGKiKfDTKDwkkwd8F2wcERGJlWgK/Ffu/mzgSUREJKZKu4omJ/J2qZmNB54G9h4c7+6rA84mIiIVUFoP/q9HfM4t8t6Bc2MfR0REYqW0q2h6VmYQCcbLj0zgw9XLqZ6SSv30Fpw3ZBQ1ateNd6ykkwzrMRkyTv3LH3lt2fOkpKbSrGUWt/55AnXq1Y93rNCK5lEFNxfzGmxm2ZURUCqm5elnMXDcE1wx9nEanJhJ3vyH4h0pKSXDekyGjDldz+HBucuYOmcpzTNb8+iD95Y9kxyzaE6y5kZeCyKfewMrgWvNbLa73xVUOCmfWVMm8ML82TQ5sRn1j29E29M6ktGp36Hx6SedzqY3lsQxYXJYNXca7770DHUappNW73iatGpHTu+rDo1PhPWYrBn7jfz+KSenntGZFc8tjGPC8IvmWTSNgBx3v8Xdb6Gw2DcBegC/DDCblMPGt99k2bNzeeDJ5/nDPdPZuH7tUdNseHE+mWd0i0O65PHZhxvY+OpiBoyexcXDxvPZ5rePmibe6zEsGRc//ShndtepvCBF04PPAPYV+bwfyHT3PWa2t4R5pJKtz3udbuddRM20WgB07fnjw8avmjuNatWr07bbRfGIlzS2vruGNmf2JLVGGgBZOeccNj4R1mMYMs6aMoHqKSmc1+fSeMSrMqIp8I8Ar5nZvMjnnwCPmllt4J3Akkm5mVmxwzcsX8CHa1ZwyR0PlDiNFJUM6zF5Mz4393Fef/F57po2OwEyhluZh2jc/U/A/wA7ga+Aa939Tnff5e6DSprPzGqa2Rtm9qaZvW1mf4xdbDlSh9wuvLzkWfZ+u4fdu77h1WXPAfDRm6+wesEM+tzyt0O9KSlZs3ad2LxqKQX7vmXfnl1sWb0cSKz1mMwZV674F49Pm8idE2cc+mtTgmPuXvwIs3ru/rWZNSxuvLt/UWrDhb+aa7v7N2aWCrwE3OTur5U0T25urq9atSr69CHzwjvbKzT/wZOsJzRrQZP0pmS2acvjD0/nu/37qVmn8FK09JM60HPwHSW2sWDdtgplAPhJx6YxbTPW7RXXZlEHTw7WbXQidRqlc3zzVry95KlyrcegxSJjPNbjlhXz2L9/H3XrHw8Unmgd9oeKXadxfvv0Cs2f7Mwsz91zixtX2iGaR4A+FD6Dxok8ZKzIz1IfNuaFvzm+iXxMjbyK/20iMTHommEMumYYADMnjQfgyrvnlTaLFCP3ksHkXjIYgNefmgJEtx7bvLuGM1b+i6evvCVmWXo/cT+bT8lmwxk/jEnGylRcxhmLSuzfSQBKu9GpT+Rnq2Nt3MyqU/gL4iRgkru/Xsw0Q4AhABkZGce6qCrp6pkl/7Wz882tWGoa9auX3kv7+1WH/+KPRa+uX3bzmLYZ6/aKa7Okdblzez6WWsCnZSzz71fl0vKtf3LKokeod1l/vuzSvcIZ6254i7PmTWPzNb+lbfZlMclYVDzWY2n/Z+HojFIxZZ5kjRxqGQS0cvc/mVkGcKK7v1HWvO7+HZBtZg2AOWZ2uruvP2KaqcBUKDxEcyz/CDlag7NLPD0i5VCe9fjp5VeS+Y8HOOmeMaw862yo4AnE1veNY3+9+vz7l9fGLGO8JEPGMIrmOvj7ga7AwMjnfGBSeRbi7juBZcCF5ZlPJJkcqFGTzdfeTP11q2m89LkKtVV/zUqavPgCH/36egp0K78co2gK/Fnufj3wLYC7fwkcV9ZMZtYk0nPHzNKA84F3K5BVJOFtu2QAu1tm0ea+cXDgwLE14k6be8awt1Fj/j1ocGwDSpUSTYHfHzmW7lBYuIFo/uc2pfBRw+sofLTB8+6u+5Il1Dw1lU1Db6PuxndIXzT/mNpo+NoKGq58hS1DhnGgVu0YJ5SqJJoCfy8wBzjBzEZTeLnj/5Y1k7uvc/dO7t7R3U939zsrmFUkKWy/+BK+ObkdrSeNxwoKyjdzpPf+7YnN+eTyK4MJKFVGNDc6zQJuA8YA24BL3H120MFEkla1amy64XfU3rKJpvOfKNesjZc+R/231rD5Nzfjx9UIKKBUFdH04AHep7AXPx/YFbmSRkRK8Pm5F/LV6dm0uv+v2L4oH9l04ABt7hvL7oxWbOt3ebABpUqI5nnwNwDbgeeBhcAzkZ8iUhIzNt04grRtn9Ji9sNRzZL+7DzqbtzApuuH46mpAQeUqiCaHvxNwCnuflrkeHoHd+8YdDCRZPfFD8/hy9wuZE25h2q7d5U6rRUU0HrSeL45uR3bL76kkhJK2EVT4D+m8CFjIlIeZnxw4+3U+O/ntHxkeqmTNp33BLU/2symG0dAtWiPnIqUrsQ7Wc3s5sjbzcAyM3sGOHQw0d3vDjibSNL7qvNZ7Oh+LlnTJvHJgF/wXd16R01j+/bS6oG/8lWHTnx+xHP8RSqitK5C3cjr3xQefz+uyLDE+iZfkQS26cYRpH69k8wZk4sd32L2w6Rt+7Sw967no0sMlfawMT2/XSQG8tt3ZHuv3mTMmMLHgwaz//hGh8ZV272LrCn38OWZXfmia484ppQw0sE+kUqweehtVN+zm8xpEw8b3vKR6dT47+d8cOPt6r1LzKnAi1SCXSedwn9+ciktH3mI4z77DwApX39F1rRJ7Oh+Ll/l/CDOCSWMorkO/qhvdDKzY35GvEhVtfm64dh3BbSa/DcAMmZMJvXrnYXH3kUCEE0PfoGZHTr1b2btgQXBRRIJpz0tM9l66UCaPzWLuuvXkjFzKtsv6EN+e91WIsGIpsD/L4VFvo6ZdQZmAz8PNpZIOH14zW/x6imcdseNVP92D5uG3hbvSBJiZX6jk7s/E/nS7OcovDzyEnd/P/BkIiG0N70p2/peRvPZD/N5zx+zu03beEeSECvtRqf7OPxLsutReNPTDWaGu98YdDiRMLJ9+wCoVt5HCYuUU2k9+CO/HTcvyCAiVUHaxx/R9JmnyG/fgcYrllB3w1vkn9oh3rEkpEq70WkGgJnVBr6NfIE2kW930oOqRY5Bq/v/gldPYf3YSZz58760uXcsax+YFe9YElLRnGRdAqQV+ZwGvBBMHJHwqrVpI00XPsUnV/yS3W3asuXX19N4+RLqr1kZ72gSUtEU+Jru/s3BD5H3tYKLJBJObSbexXc109hy9Q0AfDzo1+xt1IQ294wB9zLmFim/aAr8LjPLOfghcqnknuAiiYRP3Q1vkf7cQv591ZBDz6I5UKs2W4bcRMOVr9DwtRVxTihhFE2BHwbMNrMVZrYCeBwYGmwskXBpc+9Y9tdrwEe//M1hwz+5/Eq+PbG5evESiGi+dHsl0A74DXAdcKq764oakSjVX/0GjZcvYcvg6496HrwfV4PN191C/bfW0GTp4jgllLCK9mFjpwDtgU7AFWZ2VXCRRELEnZPuHcPeRk34eOCvi51kW7/L2ZXZmtb3jYMDByo5oIRZNA8b+wNwX+TVE7gL6BtwLpFQaPjqco5f+SpbrrmJA7VqFzuNp6Sw+frh1N24gfRn51VyQgmzaHrwPwXOA/7j7r8CzkDXwYuUzZ0294xhT9PmfHLZlaVOuv2ifuS3PZXWk8ZjusNVYqTMZ9EAe9z9gJkVRJ4q+RnQOuBcVdLUv/yR15Y9T0pqKs1aZnHrnydQp179eMeSY9Rk6WLqr1/LO3fejR93dJ/oyO09ZvBQuv/ueprOe4Ktlw6MQ+LkNHz4cBYsWMBxxx1HmzZteOihh2jQoEG8YyWEaHrwq8ysAfAghY8rWA28EWiqKiqn6zk8OHcZU+cspXlmax598N54R5JjdeAAbe4dy67M1mzrd3mxkxy5vSe+9w5fdehE6/v/iu3bW+w8crRevXqxfv161q1bR9u2bRkzZky8IyWMaJ4meV3k7WQzWwTUc/d1wcYKv9GjRzNz5kxatmxJkyZN6Ny5M7kXf/9n/KlndGbFcwvjmFAqIv2fc6nz/ru8NX4ynpLCrCkTeGH+bJqc2Iz6xzei7WkduexX1x2a/uD23nTT7eRcfTktnniYj39+dRz/BYmpuPU4Zfz3Xx/dpUsXnnzyyTgmTCzRnGRdcvC9u29x93VFh0n55eXl8dhjj7FmzRqefvppVq48+lb1xU8/ypndz41DOqko27+fNpPGk9+2Pdsv7MvGt99k2bNzeeDJ5/nDPdPZuH7tUfMc3N5fdOnOF2f+kKypE6i2e1cc0ieuaNbj9OnTueiii+KQLjGVWODNrGbk6/oam9nxZtYw8soCmlVWwDBasWIF/fv3p1atWtSrV4++fQ+/KGnWlAlUT0nhvD6XximhVETTeU9Q698fsumG30G1aqzPe51u511EzbRa1K5Tl649f3zY9IdtbzM23XQ7Nf67g5azpsfpX5CYylqPo0ePJiUlhUGDBsUpYeIp7RDNNRTexdqMwmPvB7/y/WtgUsC5Qs/Mih3+3NzHef3F57lr2uwSp5HEZfv20vqBu/mqQyd29Lzg++Hl2N5fdTqTHT3OI2v6JD4dcBUFOtF+SEnrccaMGSxcuJAlS5ZovymixB68u9/j7q2AW929tbu3irzOcPeJZTVsZi3NbKmZbTCzt83sppgmT2I9evRgzpw57Nmzh/z8fBYsKPyK25Ur/sXj0yZy58QZ1EzT89ySUYsnHqbmfz5l0023Q6TQdMjtwstLnmXvt3vYvesbXl32HFD69t504whSv95JxozJlf5vSFQlrcdFixYxbtw45s+fT61a2m+KiuYyyf+YWV13zzez/wfkAH9299VlzFcA3OLuq82sLpBnZs+7+zsVDZ3scnJyGDBgANnZ2WRmZtK9e3cAJo6+g/379/G7qwcAhSfehv3hrnhGlXKotnsXWVMn8MWZP+SLLt0PDT+5fUfOubAf1156Pic0a0GHzmcBpW/v/FM7sP2CPmTMnMrHgwazv2Hjyv8HJZiS1uPQoUPZu3cvvXr1AgpPtE6erF+MEF2B/727zzazs4EfA38BHgDOKm0md98GbIu8zzezDUBzoMoXeICRI0cycuRIAEaNGgXAjEWvxTGRVFTGrGnU+O8O1t3z0KHe+0GDrhnGoGuGATBz0nig7O29aehtnPDCP8n6+328f9sfS522qihuPX7wwQfxjJTQoinw30V+9gYecPd5ZjaqPAuJnJjtBLxezLghwBCAjIyM8jSbdLJGPFPs8J0vbcRS06i/48hvSTzclrG9Y57p/PbpCd9m0mT8xWXQKI0zB/UpcVsD7HxzK5aaxuLqUWzvu+4is2tXMmOQN2nW4xFK3G8OrsdS1jUEs98ki2gK/KdmNgU4HxhnZjWI/iFlmFkd4ClgmLt/feR4d58KTAXIzc2tks9LbXC2zvqHQnZ24asM5dret9xSgUDhpv2mbNEU6suBxcCF7r4TaAgMj6ZxM0ulsLjPcvenjzmliIiUWzR3su4Gni7y+dCx9dJY4bVK04AN7n53RUKKiEj5RX2o5Rh0A64EzjWztZHXxQEuT0REiojmGPwxcfeX+P7mKBERqWRB9uBFRCSOVOBFREJKBV5EJKRU4EVEQkoFXkQkpFTgRURCSgVeRCSkVOBFREJKBV5EJKRU4EVEQkoFXkQkpFTgRURCSgVeRCSkVOBFREJKBV5EJKRU4EVEQkoFXkQkpFTgRURCSgVeRCSkVOBFREJKBV5EJKRU4EVEQkoFXkQkpFTgRURCSgW+AoYPH067du3o2LEj/fv3Z+fOnfGOJCIVFKb9WgW+Anr16sX69etZt24dbdu2ZcyYMfGOJCIVFKb9OiXeAZLF6NGjmTlzJi1btqRJkyZ07tyZW2+99dD4Ll268OSTT8YxoYiUV9j3axX4KOTl5fHYY4+xZs0aCgoKyMnJoXPnzodNM336dAYMGBCnhCJSXlVhv1aBj8KKFSvo378/tWrVAqBv376HjR89ejQpKSkMGjQoHvFE5BhUhf1aBT5KZlbs8BkzZrBw4UKWLFlS4jQikpjCvl8HdpLVzKab2Wdmtj6oZVSWHj16MGfOHPbs2UN+fj4LFiwAYNGiRYwbN4758+cf6gWISHKoCvt1kD34fwATgZkBLqNS5OTkMGDAALKzs8nMzKR79+4ADB06lL1799KrVy+g8ITM5MmT4xlVRKJUFfbrwAq8uy83s6yg2q9sI0eOZOTIkQCMGjUKgA8++CCOiUSkosK+X8f9GLyZDQGGAGRkZMQ5zfeyRjxT4ridL23EUtOYuKPkaQC2jO0d61giUkEl7dvR7teQPPt23Au8u08FpgLk5uZ6nONEpcHZyXtWXUSKF8b9WneyioiElAq8iEhIBXmZ5KPAq8ApZvaJmQ0OalkiInK0IK+iuSKotkVEpGw6RCMiElIq8CIiIaUCLyISUirwIiIhpQIvIhJSKvAiIiGlAi8iElIq8CIiIaUCLyISUirwIiIhpQIvIhJSKvAiIiGlAi8iElIq8CIiIaUCLyISUirwIiIhpQIvIhJSKvAiIiGlAi8iElIq8CIiIaUCLyISUirwIiIhpQIvIhJSKvAiIiGlAi8iElJVpsDPnj2b0047jWrVqrFq1ap4xxGRKuT3v/89HTt2JDs7mwsuuICtW7dWynKrTIE//fTTefrpp+nRo0e8o4hIFTN8+HDWrVvH2rVr6dOnD3feeWelLDelUpZSyUaPHs3MmTNp2bIlTZo0oXPnztx6663xjiUiVUBZ9WfXrl2YWaVkCV2Bz8vL47HHHmPNmjUUFBSQk5ND586d4x1LRKqA0urPyJEjmTlzJvXr12fp0qWVkid0h2hWrFhB//79qVWrFvXq1aNv377xjiQiVURp9Wf06NF8/PHHDBo0iIkTJ1ZKntAVeKDS/vwRETlSWfVn4MCBPPXUU5WSJdACb2YXmtl7ZvaBmY0IclkH9ejRgzlz5rBnzx7y8/NZsGBBZSxWRKTE+vP+++8fmmb+/Pm0a9euUvIEdgzezKoDk4BewCfASjOb7+7vBLVMgJycHAYMGEB2djaZmZl0794dgDlz5nDDDTfw+eef07t3b7Kzs1m8eHGQUUSkiimp/owYMYL33nuPatWqkZmZyeTJkyslT5AnWX8AfODumwHM7DGgHxBogYfCkxkjR44EYNSoUQD079+f/v37B71oEaniiqs/lXVI5kjm7sE0bPZT4EJ3vzry+UrgLHcfesR0Q4AhkY+nAO/FOEoz4Dtge5TTNwZ2xDhDrNtMhoxBtKmMidlesrQZj4zlrT/HItPdmxQ3IsgefHFnGo76beLuU4GpAeYoFzNb5e65idxmMmQMok1lTMz2kqXNZMgYa0GeZP0EaFnkcwugcu7PFRGRQAv8SuBkM2tlZscBPwPmB7g8EREpIrBDNO5eYGZDgcVAdWC6u78d1PJiKIjDRbFuMxkyBtGmMiZme8nSZjJkjKnATrKKiEh8hfJOVhERUYEXEQktFXhJeGaWZWbrE7W9oNpMBto2iU0FXkQkpFTgA2Rmc80sz8zejtyxWyXaDCIjkGJmM8xsnZk9aWa1Eqy9mLeZDNs6osptm6Th7noF9AIaRn6mAeuBRlWhzQDay6LwLuhukc/TgVsTpb0A20yGbV0lt02yvNSDD9aNZvYm8BqFd/WeXEXaDCLjx+7+cuT9/wFnJ1h7QbSZDNsaqua2SQqh+8q+RGFmPwLOB7q6+24zWwbUDHubQWSMOPKGjYrewBHr9mLaZjJs6yKq1LZJJurBB6c+8GVkR2oHdKkibQaRESDDzLpG3l8BvJRg7cW6zWTY1gdVtW2TNFTgg7OIwhM764A/UfgncVVoM4iMABuAX0TabQg8kGDtxbrNZNjWB1W1bZM09KgCEZGQUg9eRCSkVOBFREJKBV5EJKRU4EVEQkoFXkQkpFTgJSmZ2SsBtJllZgPLOc8dZYz/p5k1qFgykWOjyyRFIiJ3et7q7n3KMc837l6nmOFG4f51IIYRRcpFPXhJSmb2TeTnj8xsWeQJge+a2axIccXMtpjZODN7I/I6KTL8H2b20yPbAsYC3c1srZn99ojlNTWz5ZFx682su5mNBdIiw2ZF/gLYYGb3A6uBlpEMjYuMezDyJMfnzCwt0vaZkaccvmpm462KPrtcYk8FXsKgEzAMaA+0BroVGfe1u/8AmAhMKKOdEcAKd892978dMW4gsNjds4EzgLXuPgLYE5l+UGS6U4CZ7t7J3T86oo2TgUnufhqwE7g0Mvwh4Fp37wp8F+W/WaRMKvASBm+4+yeRwyFrKXw87EGPFvnZ9cgZy2El8CszGwV0cPf8Eqb7yN1LegTAh+6+NvI+D8iKHJ+v6+4Hzyk8UoGMIodRgZcw2Fvk/Xcc/pRUL+Z9AZH/+5HDOceVtQB3Xw70AD4FHjazq0qYdFc5c1pZyxY5VirwEnYDivx8NfJ+C9A58r4fkBp5nw/ULa4RM8sEPnP3B4FpQE5k1H4zSy1unmi4+5dAvpkdfLLjz461LZEjqcBL2NUws9eBm4CDJ04fBM4xszeAs/i+170OKDCzN488yQr8CFhrZmsoPHZ+T2T4VGCdmc2qQMbBwFQze5XCHv1XFWhL5BBdJimhZWZbgFx33xHvLKUxszrufvCqoBFAU3e/Kc6xJAT0jU4i8dfbzG6ncH/8CPhlfONIWKgHLyISUjoGLyISUirwIiIhpWtK3LsAAAAWSURBVAIvIhJSKvAiIiGlAi8iElL/H4kVgvOV/CNTAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((2,2),10,3.5,alpha=0.3))\n", "ax.add_patch(patches.Rectangle((3,3),8,2.5,alpha=0.5))\n", "ax.add_line(lines.Line2D([7.5,8.5],[2,3], color=\"red\"))\n", "ax.add_line(lines.Line2D([7.5,8.5],[3,2], color=\"red\"))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Instead, there are _two_ next-smallest sub-runs:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAEGCAYAAABvtY4XAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAaFklEQVR4nO3df3xUdX7v8dcHiBiUH/5AFCUJihgVMSRxxYugrGJXYREe3TYr1G33QS93H15dbZVbl3TvUndTpPaqu8WK+AALtyiuyq9oC1qKAv7ChGAuLvhjAeuKlfXeZY0sInE/94+ZhCTmx4TMyZn55v18PPLIzJwz3/P2nMzbw5kzZ8zdERGR8PSKO4CIiERDBS8iEigVvIhIoFTwIiKBUsGLiASqT9wBmjr99NO9oKAg7hix+fTzo3FHEMk6A07MiTtCrKqrqz9x98GtTcuogi8oKKCqqiruGLH5t198HHcEkaxz7UVD4o4QKzN7v61pOkQjIhIoFbyISKBU8CIigVLBi4gESgUvIhIoFbyISKAy6jRJaW7tjg/jjiBpdmPR2XFHkB5Ee/AiIoFSwYuIBEqHaCR2Lz/+IHu3b6Z3nxwGDjmHa2bPo+9J/eOOJZL1tAcvsRs26nJmLPg5N937JIPOzKd63WNxRxIJgvbgpVtVrVnC7q3PcfKpQ8gdcAqDhxdSPPk7jdOHjBjFL7dtjDGhSDi0By/d5sDeXbzz6gbKKlZwwx33cWDPW1+ZZ9dL68i/dFwM6UTCoz146Tb7d9dw3mUTyembC0BB8VXNpletWUKv3r0ZOe76OOKJBEd78NLNrNVHd22uZG/NFibd8hPMWp9HRDon0oI3s31m9n/MbIeZ9dwLvQsAQwvHsKdqE/VffM4Xhw+xb/tmAN5/8xW2Vy5jyp0PNO7di0jXdcchmonu/kk3LEcy3BnDL+T8sdexcu4M+p92JkMLxwCwedkCvjx6lLXzbwFgyIhLmDhrbpxRRYKgY/DSrUqnzaJ02iwAXn/mEQBuvn9tnJFEghV1wTvwvJk58Ii7L245g5nNBmYD5OXlRRxH4lBZ+1Grjx/8uA7LqefDNqY3+Obos6KIJRK8qAt+nLvvN7MzgBfMbLe7b246Q7L0FwOUlpZ6xHkkgwy6cmbcEUSCFumbrO6+P/n7ALAa+FqUyxMRkWMiK3gzO8nM+jfcBq4Ddka1PBERaS7KQzRDgNXJc5r7AI+7+/oIlyciIk1EVvDuvge4NKrxRUSkffokq4hIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKB0pdui8Rs7Y4P446QVW4sOjvuCFlDe/AiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEqXKpBOefnxB9m7fTO9++QwcMg5XDN7Hn1P6h93rK/IlpyZTusxu2kPXjpl2KjLmbHg59x075MMOjOf6nWPxR2pVdmSM9NpPWY37cFLm6rWLGH31uc4+dQh5A44hcHDCyme/J3G6UNGjOKX2zbGmDAhW3JmOq3H8GgPXlp1YO8u3nl1A2UVK7jhjvs4sOetr8yz66V15F86LoZ0x2RLzkyn9Rgm7cFLq/bvruG8yyaS0zcXgILiq5pNr1qzhF69ezNy3PVxxGuULTkzndZjmLQHL+2wVh/dtbmSvTVbmHTLTzBrfZ7ulS05M53WY2giL3gz621mNWb2bNTLkvQZWjiGPVWbqP/ic744fIh92zcD8P6br7C9chlT7nygcW8vTtmSM9NpPYapOw7R3A7sAgZ0w7IkTc4YfiHnj72OlXNn0P+0MxlaOAaAzcsW8OXRo6ydfwsAQ0ZcwsRZc5Uzy2k9hinSgjezc4DJQAXwl1EuS9KvdNosSqfNAuD1Zx4B4Ob718YZqVXZkjPTaT2GJ+o9+AeB/wG0+ckIM5sNzAbIy8uLOI50pLL2o1YfP/hxHZZTz4dtTG/qm6PPSnesZtrKCKnnjDpjNtB6DF9kBW9mU4AD7l5tZle3NZ+7LwYWA5SWlnpUeaRrBl05M+4IKcmWnJlO6zEMUb7JOg6Yamb7gJXA183snyNcnoiINBFZwbv7D9z9HHcvAL4N/Lu7/0lUyxMRkeZ0HryISKC65ZOs7v4i8GJ3LEtERBK0By8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoDoseDP7o1QeExGRzJLKHvwPUnxMREQySJtf+GFm1wM3AGeb2c+aTBoA1EcdTEREuqa9b3TaD1QBU4HqJo/XAX8RZSgREem6Ngve3d8E3jSzx939aDdmEhGRNEjlO1m/ZmbzgPzk/Aa4u58bZTAREemaVAp+CYlDMtXAl9HGERGRdEml4H/r7v8aeRIREUmr9s6iKU7e3GRm9wGrgCMN0919e8TZRESkC9rbg/9fLe6XNrntwNfTH0dERNKlvbNoJnZnEInGy48/yN7tm+ndJ4eBQ87hmtnz6HtS/7hjZZ1sWI/KKC11eAzezP6ylYd/C1S7+470R5J0Gjbqcq4ou5VevfvwyhM/o3rdY/yXm74fd6yskw3rURmlpVTeZC1N/lQm708G3gC+Z2ZPufvfRRVOOqdqzRJ2b32Ok08dQu6AUxg8vJDiyd9pnD5kxCh+uW1jjAmzQzasR2WUVKRyLZrTgGJ3v9Pd7yRR9oOBCcCfRZhNOuHA3l288+oGyipWcMMd93Fgz1tfmWfXS+vIv3RcDOmyRzasR2WUVKWyB58HfNHk/lEg390Pm9mRNp4j3Wz/7hrOu2wiOX1zASgovqrZ9Ko1S+jVuzcjx10fR7yskQ3rURklVakU/OPAa2a2Nnn/m8ATZnYS8IvIkslxsFYf3bW5kr01W5g292HMWp9HmsqG9aiM0rEOD9G4+4+B/wocJPHm6vfc/R53P+TuM9t6npmdaGbbzOxNM3vLzP4mfbGlpaGFY9hTtYn6Lz7ni8OH2Ld9MwDvv/kK2yuXMeXOBxr3pqRt2bAelVFS1d4HnQa4+6dmdiqwN/nTMO1Ud/9/HYx9BPi6u39mZjnAVjP7V3d/LS3JpZkzhl/I+WOvY+XcGfQ/7UyGFo4BYPOyBXx59Chr598CwJARlzBx1tw4o2a0bFiPyiipau8QzePAFBLXoHGSFxlr8rvdi425uwOfJe/mJH+8i3mlHaXTZlE6bRYArz/zCAA337+2vadIK7JhPSqjpKK9DzpNSf4efryDm1lvEv+DGAE85O6vtzLPbGA2QF5e3vEuqkeqrP2ozWkHP67Dcur5sJ15AL45+qx0x8pKba3LTFqPyiidlcoHnQyYCQx39x+bWR5wprtv6+i57v4lUGRmg4DVZjbK3Xe2mGcxsBigtLRUe/hpMujKNt8ekU7IhvWojNKWVM6D/0fgCmBG8n4d8FBnFuLuB4EXgW905nkiInL8Uin4y939vwOfA7j7b4ATOnqSmQ1O7rljZrnAtcDuLmQVEZFOSOU8+KPJY+kOieIGfp/C884CliWf2wv4ubs/e9xJRUSkU1Ip+J8Bq4EzzKwC+Bbw1x09yd1rgTFdiyciIserw4J39xVmVg1cQ+IUyWnuvivyZCIi0iWp7MEDvAt82jC/meW5+39ElkpERLosldMkbwN+BHxM4ku3Gz7oNDraaCIi0hWp7MHfDlzg7v836jAiIpI+qZwm+QGJi4yJiEgWae9iYw1f1bcHeNHMniNxATEA3P3+iLOJiEgXtHeIpuGbcP8j+XMCKXzASUREMkN7FxvT9dtFRLJYKsfgRUQkC6ngRUQC1WHBJ7/RqeVjx32NeBER6R6p7MFXmtmAhjtmdhFQGV0kERFJh1QK/m9JlPzJZlYCPAX8SbSxRESkq1K52NhzyS/Nfp7EqZPT3P3dyJOJiEiXtPdBp3+g+ZdkDyDxoafbzAx3/37U4URE5Pi1twdf1eJ+dZRBREQkvdr7oNMyADM7Cfg8+QXaJL+hqW/3xBMRkeOVypusG4HcJvdzgX+LJo6IiKRLKgV/ort/1nAnebtfdJFERCQdUin4Q2ZW3HAneark4egiiYhIOqTyhR93AE+Z2f7k/bOAsugiiYhIOqRyHvwbZlYIXEDi6/p2u/vRyJOJiEiXpPql2xcAFwEnAmOS58Evjy6WiIh0VSpfuv0j4GoSBf8vwPXAVkAFLyKSwVJ5k/VbwDXAf7r7d4FL0XnwIiIZL5VDNIfd/fdmVp+8quQB4NyIc/VIi//+b3jtxRfok5PD0GEFXFT2V/Q9qX/HT5Ss1LC9f1cPA4ecwzWz52l7H4c5c+ZQWVnJCSecwHnnncdjjz3GoEGD4o6VEVLZg68ys0HAoyQuV7Ad2BZpqh6q+IqreHTNiyxevYmz88+let1jcUeSCDVs75vufZJBZ+Zrex+nSZMmsXPnTmpraxk5ciTz58+PO1LGSOUsmluSNxeZ2XpggLvXRhsrfBUVFSxfvpxhw4YxePBgSkpKKL3h5sbpF15awo4nfx5jQkmnqjVL2L31OV7Oz2PgKacx8uLR/NF3b2mcPmTEKH65bWOMCbND1ZolrCnfwOAzhzaux0fuO/b10WPHjuXpp5+OMWFmSeUbnRr/6tx9n7vXNn1MOq+6upqVK1dSU1PDqlWreOONN74yz4ZVT5B/6bgY0km6Hdi7i3de3UBZxQp+9NOlvLNzx1fm2fXSOm3vDjSsx4effqHN9bh06VKuv/76GNJlpvYuF3wiiUsSnG5mp5A4Bx4Slw0e2g3ZgrVlyxamT59Ov36JKz5MnTq12fQVjzxI7z59GDlOf6gh2L+7hvMum0hO31xOOrk/V0z8g2bTq9YsoVfv3treHWhYjyfmJl43LddjRUUFffr0YebMmXHEy0jtHaL5byQ+xTqUxLH3hoL/FHgo4lzBM7NWH39+zZO8/tIL/N2Sp9jw9m+6OZVEp+3tvbdmC9PmPtzm34Q01fo6WrZsGc8++ywbN27UemyizUM07v5Tdx8O3OXu57r78OTPpe6+sKOBzWyYmW0ys11m9paZ3Z7W5FlswoQJrF69msOHD1NXV0dlZeIrbt/Y8u88uWQh9yxc1riXItlvaOEY9lRtov6Lz/ndoc949cXngWPbe8qdD5DTN7eDUaRhPR75/HCz9bh+/XoWLFjAunXrGv9VLAmpnCb5n2bW393rzOyvgWLgJ+6+vYPn1QN3uvt2M+sPVJvZC+7+i66GznbFxcWUlZVRVFREfn4+48ePB2BhxVyOHv2Cv/rzxKV+cs8uZOKsuXFGlTQ4Y/iFnD/2OlbOncG24QVcUnI5cGx7r52feLN1yIhLtL3b0bAev/eH13LG0HMa1+Ott97KkSNHmDRpEpB4o3XRokVxRs0YqRT8D939KTO7EvgD4O+Bh4HL23uSu38EfJS8XWdmu4CzgR5f8ADl5eWUl5cDMG/ePACWrX+t2Txrd3zY3bEkIqXTZlE6bRY3Fp3N8ofuA45tb23n1JVOm8WP5/1PgMb1+N5778UZKaOlUvBfJn9PBh5297VmNq8zCzGzAmAM8Hor02YDswHy8vI6M2zWKbj7uVYfP7j1HSwnl4GftPyWxOb23Tu52f3K2tbH64x/mFHc7H4mjpmNGdva1pW1H3Hwzf1YTi4benfv9s7G9QhfXZeVtR8BHFuPbazrBi3XY0+SSsF/aGaPANcCC8ysL6l9QAoAMzsZeAa4w90/bTnd3RcDiwFKS0u95fSeYNCVete/J9H2Tg+tx46lUtR/DGwAvuHuB4FTgTmpDG5mOSTKfYW7rzrulCIi0mmpfJL1d8CqJvcbj623xxLnKi0Bdrn7/V0JKSIinZfyoZbjMA64Gfi6me1I/twQ4fJERKSJVL/wo9PcfSttfSpBREQiF+UevIiIxEgFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFLyISKBW8iEigVPAiIoFSwXfBnDlzKCwsZPTo0UyfPp2DBw/GHUlEuiik17UKvgsmTZrEzp07qa2tZeTIkcyfPz/uSCLSRSG9rvvEHSBbVFRUsHz5coYNG8bgwYMpKSnhrrvuapw+duxYnn766RgTikhnhf66VsGnoLq6mpUrV1JTU0N9fT3FxcWUlJQ0m2fp0qWUlZXFlFBEOqsnvK5V8CnYsmUL06dPp1+/fgBMnTq12fSKigr69OnDzJkz44gnIsehJ7yuVfApMrNWH1+2bBnPPvssGzdubHMeEclMob+uI3uT1cyWmtkBM9sZ1TK6y4QJE1i9ejWHDx+mrq6OyspKANavX8+CBQtYt25d416AiGSHnvC6jnIP/p+AhcDyCJfRLYqLiykrK6OoqIj8/HzGjx8PwK233sqRI0eYNGkSkHhDZtGiRXFGFZEU9YTXdWQF7+6bzawgqvG7W3l5OeXl5QDMmzcPgPfeey/GRCLSVaG/rmM/Bm9ms4HZAHl5eTGnOabg7ufanHZw6ztYTi4LP2l7HoB9905OdywR6aK2Xtupvq4he17bsRe8uy8GFgOUlpZ6zHFSMujK7H1XXURaF+LrWp9kFREJlApeRCRQUZ4m+QTwKnCBmf3KzGZFtSwREfmqKM+iuSmqsUVEpGM6RCMiEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEigVvIhIoFTwIiKBUsGLiARKBS8iEqgeU/BPPfUUF198Mb169aKqqiruOCLSg/zwhz9k9OjRFBUVcd1117F///5uWW6PKfhRo0axatUqJkyYEHcUEelh5syZQ21tLTt27GDKlCncc8893bLcPt2ylG5WUVHB8uXLGTZsGIMHD6akpIS77ror7lgi0gN01D+HDh3CzLolS3AFX11dzcqVK6mpqaG+vp7i4mJKSkrijiUiPUB7/VNeXs7y5csZOHAgmzZt6pY8wR2i2bJlC9OnT6dfv34MGDCAqVOnxh1JRHqI9vqnoqKCDz74gJkzZ7Jw4cJuyRNcwQPd9s8fEZGWOuqfGTNm8Mwzz3RLlkgL3sy+YWZvm9l7ZnZ3lMtqMGHCBFavXs3hw4epq6ujsrKyOxYrItJm/7z77ruN86xbt47CwsJuyRPZMXgz6w08BEwCfgW8YWbr3P0XUS0ToLi4mLKyMoqKisjPz2f8+PEArF69mttuu41f//rXTJ48maKiIjZs2BBlFBHpYdrqn7vvvpu3336bXr16kZ+fz6JFi7olT5Rvsn4NeM/d9wCY2UrgRiDSgofEmxnl5eUAzJs3D4Dp06czffr0qBctIj1ca/3TXYdkWjJ3j2Zgs28B33D3P0/evxm43N1vbTHfbGB28u4FwNtpjjIU+BL4OMX5Twc+SXOGdI+ZDRmjGFMZM3O8bBkzjoyd7Z/jke/ug1ubEOUefGvvNHzl/ybuvhhYHGGOTjGzKncvzeQxsyFjFGMqY2aOly1jZkPGdIvyTdZfAcOa3D8H6J7P54qISKQF/wZwvpkNN7MTgG8D6yJcnoiINBHZIRp3rzezW4ENQG9gqbu/FdXy0iiKw0XpHjMbMkYxpjJm5njZMmY2ZEyryN5kFRGReAX5SVYREVHBi4gESwUvGc/MCsxsZ6aOF9WY2UDbJrOp4EVEAqWCj5CZrTGzajN7K/mJ3R4xZhQZgT5mtszMas3saTPrl2HjpX3MbNjWST1u22QNd9dPRD/AqcnfucBO4LSeMGYE4xWQ+BT0uOT9pcBdmTJehGNmw7bukdsmW360Bx+t75vZm8BrJD7Ve34PGTOKjB+4+8vJ2/8MXJlh40UxZjZsa+iZ2yYrBPeVfZnCzK4GrgWucPffmdmLwImhjxlFxqSWH9jo6gc40j1eWsfMhm3dRI/aNtlEe/DRGQj8JvlCKgTG9pAxo8gIkGdmVyRv3wRszbDx0j1mNmzrBj1t22QNFXx01pN4Y6cW+DGJfxL3hDGjyAiwC/jT5LinAg9n2HjpHjMbtnWDnrZtsoYuVSAiEijtwYuIBEoFLyISKBW8iEigVPAiIoFSwYuIBEoFL1nJzF6JYMwCM5vRyefM7WD6v5jZoK4lEzk+Ok1SJCn5Sc+73H1KJ57zmbuf3MrjRuL19fs0RhTpFO3BS1Yys8+Sv682sxeTVwjcbWYrkuWKme0zswVmti35MyL5+D+Z2bdajgXcC4w3sx1m9hctlneWmW1OTttpZuPN7F4gN/nYiuS/AHaZ2T8C24FhyQynN5n2aPJKjs+bWW5y7MuSVzl81czusx567XJJPxW8hGAMcAdwEXAuMK7JtE/d/WvAQuDBDsa5G9ji7kXu/kCLaTOADe5eBFwK7HD3u4HDyflnJue7AFju7mPc/f0WY5wPPOTuFwMHgT9MPv4Y8D13vwL4MsX/ZpEOqeAlBNvc/VfJwyE7SFwetsETTX5f0fKJnfAG8F0zmwdc4u51bcz3vru3dQmAve6+I3m7GihIHp/v7+4N7yk83oWMIs2o4CUER5rc/pLmV0n1Vm7Xk/zbTx7OOaGjBbj7ZmAC8CHwv83sO23MeqiTOa2jZYscLxW8hK6sye9Xk7f3ASXJ2zcCOcnbdUD/1gYxs3zggLs/CiwBipOTjppZTmvPSYW7/waoM7OGKzt++3jHEmlJBS+h62tmrwO3Aw1vnD4KXGVm24DLObbXXQvUm9mbLd9kBa4GdphZDYlj5z9NPr4YqDWzFV3IOAtYbGavktij/20XxhJppNMkJVhmtg8odfdP4s7SHjM72d0bzgq6GzjL3W+POZYEQN/oJBK/yWb2AxKvx/eBP4s3joRCe/AiIoHSMXgRkUCp4EVEAqWCFxEJlApeRCRQKngRkUD9f0P/jX14qgElAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "fig, ax = plt.subplots()\n", "plot_height(ax, r.shortest_path())\n", "ax.add_patch(patches.Rectangle((2,2),10,3.5,alpha=0.3))\n", "ax.add_patch(patches.Rectangle((2.2,2),5.7,3.3,alpha=0.5))\n", "ax.add_patch(patches.Rectangle((8.1,2),3.7,2.5,alpha=0.5))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So we should add a rule $A_{q_2q_2} \\rightarrow A_{q_2q_2} A_{q_2q_2}$.\n", "\n", "Finally, there are also sub-runs of length 0, so we should add a rule $A_{q_2q_2} \\rightarrow \\varepsilon$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The general construction\n", "\n", "The PDA to CFG construction does this, but not for a particular string; it does this for all possible strings. It starts by putting the PDA into a well-behaved form:\n", "\n", "1. If there is more than one accept state, create a new accept state $f'$, make all the old accept states into non-accept states, and add $\\varepsilon,\\varepsilon\\rightarrow\\varepsilon$ transitions from every old accept state to $f'$ like this:\n", "\n", "![Making the PDA have a single accept state](single_accept.pdf)\n", "\n", "2. If the PDA potentially accepts with a non-empty stack, add states and transitions like this:\n", "\n", "![Making the PDA empty the stack before accepting](empty_stack.pdf)\n", "\n", "where state $e$ has many self-loops, one for each stack symbol $x \\in \\Gamma$.\n", "\n", "3. If the PDA has any transitions that both push and pop, break them into two transitions like this:\n", "\n", "![Removing a pop-push transition](pop_push.pdf)\n", "\n", "Similarly, if the PDA has any transitions that neither push nor pop, break them into two transitions like this:\n", "\n", "![Removing a no-op transition](noop.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then, the construction creates CFG rules of three types.\n", "\n", "1. For each pair of transitions of the form\n", "\n", "![A pair of push and pop transitions](transition_pair.pdf)\n", "\n", "(where $a$ could be $\\epsilon$), create the rule\n", "\n", "$$ A_{pq} \\rightarrow a A_{rs} b $$\n", "\n", "2. For all states $p, q, r$, create the rule\n", "\n", "$$ A_{pq} \\rightarrow A_{pr} A_{rq} $$\n", "\n", "3. For each state $p$, create the rule\n", "\n", "$$ A_{pp} \\rightarrow \\varepsilon $$\n", "\n", "Here's what the construction looks like on our example PDA:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "start: (start,accept)
\n", "(q1,q3) → (q2,q2)
\n", "(q1,empty) → (q2,q3)
\n", "(q1,empty) → (q2,empty)
\n", "(start,accept) → (q1,q3)
\n", "(start,accept) → (q1,empty)
\n", "(q2,q2) → a (q2,q2) b
\n", "(q2,empty) → a (q2,q3)
\n", "(q2,empty) → a (q2,empty)
\n", "(q1,q1) → (q1,q1) (q1,q1)
\n", "(q1,q1) → (q1,q2) (q2,q1)
\n", "(q1,q1) → (q1,q3) (q3,q1)
\n", "(q1,q2) → (q1,q1) (q1,q2)
\n", "(q1,q2) → (q1,q2) (q2,q2)
\n", "(q1,q2) → (q1,q3) (q3,q2)
\n", "(q1,q3) → (q1,q1) (q1,q3)
\n", "(q1,q3) → (q1,q2) (q2,q3)
\n", "(q1,q3) → (q1,q3) (q3,q3)
\n", "(q2,q1) → (q2,q1) (q1,q1)
\n", "(q2,q1) → (q2,q2) (q2,q1)
\n", "(q2,q1) → (q2,q3) (q3,q1)
\n", "(q2,q2) → (q2,q1) (q1,q2)
\n", "(q2,q2) → (q2,q2) (q2,q2)
\n", "(q2,q2) → (q2,q3) (q3,q2)
\n", "(q2,q3) → (q2,q1) (q1,q3)
\n", "(q2,q3) → (q2,q2) (q2,q3)
\n", "(q2,q3) → (q2,q3) (q3,q3)
\n", "(q3,q1) → (q3,q1) (q1,q1)
\n", "(q3,q1) → (q3,q2) (q2,q1)
\n", "(q3,q1) → (q3,q3) (q3,q1)
\n", "(q3,q2) → (q3,q1) (q1,q2)
\n", "(q3,q2) → (q3,q2) (q2,q2)
\n", "(q3,q2) → (q3,q3) (q3,q2)
\n", "(q3,q3) → (q3,q1) (q1,q3)
\n", "(q3,q3) → (q3,q2) (q2,q3)
\n", "(q3,q3) → (q3,q3) (q3,q3)
\n", "(q1,q1) → ε
\n", "(q2,q2) → ε
\n", "(q3,q3) → ε" ], "text/plain": [ "" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_grammar(mc)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(Tock writes the state $A_pq$ as $(p, q)$.) The grammar is really big! The first reason is that Tock added states to make the PDA empty the stack before accepting, even though it already does so. The second reason is that there are many rules of the second type. To avoid having to write so many, we can skip any rules involving nonterminals that we know can never be used. Here's one way to do that. First, create rules of the first and third type:\n", "\n", "\\begin{align*}\n", "A_{13} &\\rightarrow A_{22} \\\\\n", "A_{22} &\\rightarrow \\texttt{a} A_{22} \\texttt{b} \\\\\n", "A_{11} &\\rightarrow \\epsilon \\\\\n", "A_{22} &\\rightarrow \\epsilon \\\\\n", "A_{33} &\\rightarrow \\epsilon\n", "\\end{align*}\n", "\n", "Then, look at the left-hand sides of the rules. If there is a left-hand side $A_{pr}$ and a left-hand side $A_{rs}$, create the rule $A_{pq} \\rightarrow A_{pr} A_{rs}$.\n", "\n", "\\begin{align*}\n", "A_{13} & \\rightarrow A_{11} A_{13} \\\\\n", "A_{13} & \\rightarrow A_{13} A_{33} \\\\\n", "A_{11} & \\rightarrow A_{11} A_{11} \\\\\n", "A_{22} & \\rightarrow A_{22} A_{22} \\\\\n", "A_{33} & \\rightarrow A_{33} A_{33}\n", "\\end{align*}\n", "\n", "Repeat until no more rules can be created -- in this case, no more rules can be created after the first pass." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" } }, "nbformat": 4, "nbformat_minor": 1 }