{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 6: 2018/02/26-03/02" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "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", "2\n", "\n", "0.1\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "3\n", "\n", "loop\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "ε,ε → S\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "3->3\n", "\n", "\n", "ε,S → b\n", "ε,T → ε\n", "a,a → ε\n", "b,b → ε\n", "\n", "\n", "\n", "4\n", "\n", "1.2\n", "\n", "\n", "\n", "3->4\n", "\n", "\n", "ε,S → b\n", "\n", "\n", "\n", "6\n", "\n", "3.1\n", "\n", "\n", "\n", "3->6\n", "\n", "\n", "ε,T → a\n", "\n", "\n", "\n", "5\n", "\n", "1.1\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "ε,ε → T\n", "\n", "\n", "\n", "5->3\n", "\n", "\n", "ε,ε → a\n", "\n", "\n", "\n", "6->3\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", "2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "b\n", "\n", "\n", "\n", "1\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "a\n", "\n", "\n", "\n", "3\n", "\n", "\n", "\n", "3->1\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "\n", "\n", "4->3\n", "\n", "\n", "a\n", "\n", "\n", "\n", "8\n", "\n", "0.1,$\n", "\n", "\n", "\n", "5->8\n", "\n", "\n", "\n", "\n", "\n", "6\n", "\n", "1.2,[b] $\n", "\n", "\n", "\n", "11\n", "\n", "1.1,[T] b $\n", "\n", "\n", "\n", "6->11\n", "\n", "\n", "\n", "\n", "\n", "7\n", "\n", "loop,[T] b $\n", "\n", "\n", "\n", "13\n", "\n", "3.1,[a] b $\n", "\n", "\n", "\n", "7->13\n", "\n", "\n", "\n", "\n", "\n", "14\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "7->14\n", "\n", "\n", "\n", "\n", "\n", "9\n", "\n", "loop,[S] $\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "\n", "\n", "\n", "9->6\n", "\n", "\n", "\n", "\n", "\n", "10\n", "\n", "loop,[b] $\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "\n", "\n", "\n", "12\n", "\n", "loop,[a] T b …\n", "\n", "\n", "\n", "11->12\n", "\n", "\n", "\n", "\n", "\n", "12->7\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 b …\n", "\n", "\n", "\n", "28->30\n", "\n", "\n", "\n", "\n", "\n", "31\n", "\n", "loop,[a] a a …\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\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": 15, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "%3\n", "\n", "\n", "\n", "_START\n", "\n", "\n", "\n", "4\n", "\n", "start\n", "\n", "\n", "\n", "_START->4\n", "\n", "\n", "\n", "\n", "\n", "0\n", "\n", "loop\n", "\n", "\n", "\n", "0->0\n", "\n", "\n", "ε,b → S\n", "ε,ε → T\n", "a,ε → a\n", "b,ε → b\n", "\n", "\n", "\n", "1\n", "\n", "3.1\n", "\n", "\n", "\n", "0->1\n", "\n", "\n", "ε,a → ε\n", "\n", "\n", "\n", "2\n", "\n", "1.2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,b → ε\n", "\n", "\n", "\n", "6\n", "\n", "0.1\n", "\n", "\n", "\n", "0->6\n", "\n", "\n", "ε,S → ε\n", "\n", "\n", "\n", "1->0\n", "\n", "\n", "ε,T → T\n", "\n", "\n", "\n", "3\n", "\n", "1.1\n", "\n", "\n", "\n", "2->3\n", "\n", "\n", "ε,T → ε\n", "\n", "\n", "\n", "3->0\n", "\n", "\n", "ε,a → S\n", "\n", "\n", "\n", "4->0\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "5\n", "\n", "\n", "accept\n", "\n", "\n", "\n", "6->5\n", "\n", "\n", "ε,$ → ε\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": [ "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", "0\n", "\n", "q1\n", "\n", "\n", "\n", "_START->0\n", "\n", "\n", "\n", "\n", "\n", "2\n", "\n", "q2\n", "\n", "\n", "\n", "0->2\n", "\n", "\n", "ε,ε → $\n", "\n", "\n", "\n", "1\n", "\n", "\n", "q3\n", "\n", "\n", "\n", "2->1\n", "\n", "\n", "ε,$ → ε\n", "\n", "\n", "\n", "2->2\n", "\n", "\n", "a,ε → #\n", "b,# → ε\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", "13\n", "\n", "q1,ε\n", "\n", "\n", "\n", "_START->13\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", "7\n", "\n", "\n", "\n", "3->7\n", "\n", "\n", "a\n", "\n", "\n", "\n", "4\n", "\n", "\n", "\n", "5\n", "\n", "\n", "\n", "4->5\n", "\n", "\n", "b\n", "\n", "\n", "\n", "6\n", "\n", "\n", "\n", "5->6\n", "\n", "\n", "b\n", "\n", "\n", "\n", "8\n", "\n", "\n", "\n", "6->8\n", "\n", "\n", "a\n", "\n", "\n", "\n", "7->4\n", "\n", "\n", "b\n", "\n", "\n", "\n", "9\n", "\n", "\n", "\n", "8->9\n", "\n", "\n", "a\n", "\n", "\n", "\n", "10\n", "\n", "\n", "\n", "9->10\n", "\n", "\n", "b\n", "\n", "\n", "\n", "12\n", "\n", "\n", "\n", "10->12\n", "\n", "\n", "b\n", "\n", "\n", "\n", "11\n", "\n", "\n", "\n", "12->11\n", "\n", "\n", "b\n", "\n", "\n", "\n", "14\n", "\n", "q2,$\n", "\n", "\n", "\n", "13->14\n", "\n", "\n", "\n", "\n", "\n", "15\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "14->15\n", "\n", "\n", "\n", "\n", "\n", "16\n", "\n", "q3,ε\n", "\n", "\n", "\n", "14->16\n", "\n", "\n", "\n", "\n", "\n", "17\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "15->17\n", "\n", "\n", "\n", "\n", "\n", "18\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "17->18\n", "\n", "\n", "\n", "\n", "\n", "19\n", "\n", "q2,[#] # # # $\n", "\n", "\n", "\n", "18->19\n", "\n", "\n", "\n", "\n", "\n", "20\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "19->20\n", "\n", "\n", "\n", "\n", "\n", "21\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "20->21\n", "\n", "\n", "\n", "\n", "\n", "22\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "21->22\n", "\n", "\n", "\n", "\n", "\n", "23\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "22->23\n", "\n", "\n", "\n", "\n", "\n", "24\n", "\n", "q2,[#] # # $\n", "\n", "\n", "\n", "23->24\n", "\n", "\n", "\n", "\n", "\n", "25\n", "\n", "q2,[#] # $\n", "\n", "\n", "\n", "24->25\n", "\n", "\n", "\n", "\n", "\n", "26\n", "\n", "q2,[#] $\n", "\n", "\n", "\n", "25->26\n", "\n", "\n", "\n", "\n", "\n", "27\n", "\n", "q2,$\n", "\n", "\n", "\n", "26->27\n", "\n", "\n", "\n", "\n", "\n", "28\n", "\n", "\n", "q3,ε\n", "\n", "\n", "\n", "27->28\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": { "collapsed": true }, "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": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF7NJREFUeJzt3X9w5Hd93/Hn+5AdW/gX1LcJNZJlJsgaTKRjV4JjTFSH\nRBRzrtqd0oqipNMMnSOTyDGhUuaowqCSbs8R0zRJj0Q9N6rkxo6mPttC0hmZVLUHXUvAJyIrAsfm\n6t7FPxKDOxHIjlAt8+4f+9Vxd+jHV9J+9dXu5/WY2dHufr/7+b74ftmXv/fd737X3B0REal8+9IO\nICIiu0OFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBKIq7QAXuv76672u\nri7tGCIiZWNmZuZld98fZ949Vfh1dXWcPn067RgiImXDzM7FnVeHdEREAqHCFxEJhApfRCQQKnwR\nkUCo8EVEAqHCFxEJhApfRCQQKnwRkUCo8CV1PT09NDQ00NjYSD6fZ2FhIe1IIhVJhS+pa2trY35+\nnrm5Oerr6zl69GjakUQq0p66tIJUvkKhwPDwMJlMhpqaGnK5HN3d3eenHzx4kBMnTqSYUKRyqfBl\n18zMzDAyMsLs7CwrKytks1lyudxF8wwODtLR0ZFSQpHKpsKXXTM9PU0+n6e6uhqA9vb2i6YXCgWq\nqqro7OxMI55IxVPhy54wNDTExMQEU1NTmFnacUQqUqIf2prZWTP7czObNTNd9zhwra2tjI6OsrS0\nxOLiIuPj4wBMTk7S39/P2NjY+b1/ESm93djD/xl3f3kXliN7XDabpaOjg6amJjKZDC0tLQB0dXWx\nvLxMW1sbUPzgdmBgIM2oIhVJh3RkV/X29tLb2wtAX18fAGfOnEkxkUg4kj4P34EvmdmMmR1OeFki\nIrIBc/fkBje7wd1fMLMM8CfAne7+5UvmOQwcBqitrc2dOxf717qkTNQdObmj15+9+1CJkohUHjOb\ncffmOPMmuofv7i9Ef78NPAy8e415jrt7s7s3798f63d4RURkGxIrfDN7o5ldvXof+AAwn9TyRERk\nY0l+aPvjwMPROdVVwP3uPpng8kREZAOJFb67Pws0JTW+iIhsja6WKSISCBW+iEggVPgiIoFQ4YuI\nBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgi\nIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+\nbElPTw8NDQ00NjaSz+dZWFhIO9KayiXnXqf1WFlU+LIlbW1tzM/PMzc3R319PUePHk070prKJede\np/VYWarSDiB7V6FQYHh4mEwmQ01NDblcju7u7vPTDx48yIkTJ1JMWFQuOfc6rcfKp8KXNc3MzDAy\nMsLs7CwrKytks1lyudxF8wwODtLR0ZFSwqJyybnXaT2GQYUva5qeniafz1NdXQ1Ae3v7RdMLhQJV\nVVV0dnamEe+8csm512k9hkGFL1s2NDTExMQEU1NTmFnacdZVLjn3Oq3HypH4h7Zm9gYz+zMzm0h6\nWVI6ra2tjI6OsrS0xOLiIuPj4wBMTk7S39/P2NjY+b3BNJVLzr1O6zEMu7GHfxfwFHDNLixLSiSb\nzdLR0UFTUxOZTIaWlhYAurq6WF5epq2tDSh+kDcwMKCcZU7rMQzm7skNbvZWYBgoAJ909zs2mr+5\nudlPnz6dWB7Zvr6+Pq666qqLztqIq+7IyR0t++zdh2LPu5Oc8kNaj+XDzGbcvTnOvEkf0vkd4NeB\nHyS8HBER2URie/hmdgfwIXf/ZTO7Deheaw/fzA4DhwFqa2tz586dSySPxLPTvXH40T3yUu/hJ5Ex\nRFqPlWGv7OHfCrSb2VlgBHi/mf3RpTO5+3F3b3b35v379ycYR0QkbIkVvrt/yt3f6u51wEeA/+Hu\nP5/U8kREZGO6lo6ISCB25YtX7v448PhuLEtERNamPXwRkUCo8EVEAqHCFxEJhApfRCQQKnwRkUCo\n8EVEAqHCFxEJhApfRCQQKnwRkUCo8EVEAqHCFxEJhApfRCQQKnwRkUCo8EVEArFp4ZvZP4nznIiI\n7G1x9vA/FfM5ERHZw9b9ARQzux34EHCDmf3eBZOuAVaSDiYiIqW10S9evQicBtqBmQueXwR+LclQ\nIiJSeusWvrs/CTxpZve7+2u7mElERBIQ5zdt321mfcCN0fwGuLu/LclgIiJSWnEK/w8pHsKZAV5P\nNo6IiCQlTuF/192/mHgSERFJ1EZn6WSju4+Z2eeAh4Dl1enu/vWEs4mISAlttIf/7y953HzBfQfe\nX/o4IiKSlI3O0vmZ3QwiIiLJinNphU+ucfuYmR3YjYCyMz09PTQ0NNDY2Eg+n2dhYSHtSGWpHNaj\nMspm4lxaoRn4JeCG6PZx4IPAPWb26wlmkxJoa2tjfn6eubk56uvrOXr0aNqRylI5rEdllM3EOUvn\nrUDW3V8BMLPPACeBVoqnavYnF0+2olAoMDw8TCaToaamhlwuR3d39/npBw8e5MSJEykmLA/lsB6V\nUbYjTuFnuODsHOA14MfdfcnMltd5jeyymZkZRkZGmJ2dZWVlhWw2Sy6Xu2iewcFBOjo6UkpYHsph\nPSqjbFecwr8P+KqZfSF6/A+A+83sjcA3E0smWzI9PU0+n6e6uhqA9vb2i6YXCgWqqqro7OxMI17Z\nKIf1qIyyXZsWvrv/ppl9Ebg1euqX3P10dF9bqwwMDQ0xMTHB1NQUZpZ2nLJVDutRGWUj635oa2bX\nRH/fDDwL/Nfo9mz03IbM7Aoz+5qZPWlm3zCzf1Oq0PKjWltbGR0dZWlpicXFRcbHxwGYnJykv7+f\nsbGx83tbsr5yWI/KKNu10R7+/cAdFD+YdaKLpl3wd7OLpy0D73f3V8zsMuCUmX3R3f9057HlUtls\nlo6ODpqamshkMrS0tADQ1dXF8vIybW1tQPGDsoGBgTSj7mnlsB6VUbZroy9e3RH9vWk7A7u7A69E\nDy+Lbr6dsSSe3t5eent7Aejr6wPgzJkzKSYqT+WwHpVRtmPTY/hWPMjWCdwUHc+vBX7C3b8W47Vv\noPgvhJ8EPu/uX11jnsPAYYDa2totxg9b3ZGT605bOPUMdtmVHHt5/XkAzt59qNSxytJ663IvrUdl\nlJ2Kc5bO7wM/oHjtnN+k+ItXDwItm73Q3V8HDpjZdcDDZvZOd5+/ZJ7jwHGA5uZm/QugRK57nz5P\nL4VyWI/KKHHF+abte9z9V4DvA7j73wCXb2Uh7r4APEbxG7oiIpKCOIX/WnRoxgHMbD/FPf4Nmdn+\naM8eM7sSaAP+YgdZRURkB+Ic0vk94GEgY2YF4MPAb8R43VuA4eg/FvuA/+buE9tOKiIiOxLni1f3\nmdkM8LMUT8n8R+7+VIzXzQHv2nlEEREphTh7+ADfAr63Or+Z1br7XyaWSkRESi7OaZl3Ap8BXqL4\nI+arX7xqTDaaiIiUUpw9/LuAm939/yYdRkREkhPnLJ3ngO8mHURERJK17h6+mX0yuvss8LiZneSC\n6+K7+28nnE1EREpoo0M6V0d//zK6Xc4Wv3AlIiJ7x0YXT9PljEVEKkicY/giIlIBVPgiIoHYtPDX\n+nUrM9vWNfJFRCQ9cfbwx1d/7hDAzN4BjCcXSUREkhCn8P8dxdK/ysxywAPAzycbS0RESi3OxdNO\nRr9J+yWKp2rm3f2ZxJOJiEhJbfTFq//Ixb9Bey3wv4EuM8PdfzXpcCIiUjob7eGfvuTxTJJBREQk\nWRt98WoYwMzeCHw/+n3a1R8m/7HdiSciIqUS50PbKeDKCx5fCfz3ZOKIiEhS4hT+Fe7+yuqD6H51\ncpFERCQJcQr/VTPLrj6ITs1cSi6SiIgkIc4PoHwCeMDMXqT4a1c/AXQkmkpEREouznn4T5hZA3Bz\n9NTT7v5asrFERKTU4v6I+c3AO4ArgGx0Hv69ycUSEZFSi/Mj5p8BbqNY+I8AtwOnABW+iEgZifOh\n7YeBnwX+2t1/EWii+K1bEREpI3EKf8ndfwCsRFfN/DZQk2ysMPX09NDQ0EBjYyP5fJ6FhYW0I0mC\ntL1LQ+sxvjiFf9rMrgPuoXh5ha8DX0k0VaDa2tqYn59nbm6O+vp6jh49mnYkSZC2d2loPcYX5yyd\nX47uDpjZJHCNu88lG6vyFQoFhoeHyWQy1NTUkMvl6O7uPj/94MGDnDhxIsWEUkra3qWh9bgzcX7x\namr1vrufdfe5C5+TrZuZmWFkZITZ2VkeeeQRnnjiiR+ZZ3BwkNtvvz2FdFJq2t6lofW4cxtdHvkK\nipdQuN7M3kTxS1cA1wA37EK2ijU9PU0+n6e6uniFivb29oumFwoFqqqq6OzsTCOelJi2d2loPe7c\nRod0Pk7xW7Z/l+Kx+9XC/x5wLOFcwRoaGmJiYoKpqSnMbPMXSFnT9i4Nrcd41j2k4+6/6+43Ad3u\n/jZ3vym6Nbn7poVvZjVm9piZfdPMvmFmd5U0eRlrbW1ldHSUpaUlFhcXGR8v/kTw5OQk/f39jI2N\nnd+LkfKn7V0aWo87F+ebtn9tZle7+6KZ/QaQBf6tu399k9etAP/K3b9uZlcDM2b2J+7+zZ2GLnfZ\nbJaOjg6amprIZDK0tLQA0NXVxfLyMm1tbUDxA6iBgYE0o0oJaHuXhtbjzsUp/E+7+wNm9j7g54DP\nAX8AvGejF7n7XwF/Fd1fNLOnKB77D77wAXp7e+nt7QWgr68PgDNnzqSYSJKk7V0aWo87E+c8/Nej\nv4eA4+5+Erh8KwsxszrgXcBXt/I6EREpnTh7+C+Y2X8C2oDfMrMfI95/KAAws6uAB4FPuPv31ph+\nGDgMUFtbG3fYslR35OQ6U1rg+3Bs3elFZ+8+VPpQkoj1tzVoe2+N3jelE6e4/ynwKPD33X0BeDPQ\nE2dwM7uMYtnf5+4PrTWPux9392Z3b96/f3/M2CIislVxvmn7t8BDFzw+f2x+I1Y8N+oPgafc/bd3\nElJERHYu9qGZbbgV+AXg/WY2G90+lODyRERkA3F/AGXL3P0UP/yyloiIpCzJPXwREdlDVPgiIoFQ\n4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEgg\nVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyIS\nCBW+iEggVPg70NPTQ0NDA42NjeTzeRYWFtKOJCI7VMnvaxX+DrS1tTE/P8/c3Bz19fUcPXo07Ugi\nskOV/L6uSjtAuSgUCgwPD5PJZKipqSGXy9Hd3X1++sGDBzlx4kSKCUVkq0J7X6vwY5iZmWFkZITZ\n2VlWVlbIZrPkcrmL5hkcHKSjoyOlhCKyVSG+r1X4MUxPT5PP56murgagvb39oumFQoGqqio6OzvT\niCci2xDi+1qFv0NDQ0NMTEwwNTWFmaUdR0RKoFLf14l9aGtmg2b2bTObT2oZu6W1tZXR0VGWlpZY\nXFxkfHwcgMnJSfr7+xkbGzu/lyAi5SHE93WSe/hDwDHg3gSXsSuy2SwdHR00NTWRyWRoaWkBoKur\ni+XlZdra2oDiBzwDAwNpRhWRmEJ8XydW+O7+ZTOrS2r83dbb20tvby8AfX19AJw5cybFRCKyU6G9\nr1M/hm9mh4HDALW1tSmn+aG6IyfXnbZw6hnssis59vL68wCcvftQqWOJyA6t996O+76G8n1vp174\n7n4cOA7Q3NzsKceJ5br3Vc6n9iJSFML7Wt+0FREJhApfRCQQSZ6W+cfAV4Cbzex5M/tYUssSEZHN\nJXmWzj9LamwREdk6HdIREQmECl9EJBAqfBGRQKjwRUQCocIXEQmECl9EJBAqfBGRQKjwRUQCocIX\nEQmECl9EJBAqfBGRQKjwRUQCocIXEQmECl9EJBAqfBGRQKjwRUQCocIXEQmECl9EJBAqfBGRQKjw\nRUQCocIXEQmECl9EJBAqfBGRQKjwRUQCEUzhP/DAA9xyyy3s27eP06dPpx1HRALy6U9/msbGRg4c\nOMAHPvABXnzxxVRyBFP473znO3nooYdobW1NO4qIBKanp4e5uTlmZ2e54447+OxnP5tKjqpUlpqw\nQqHA8PAwmUyGmpoacrkc3d3daccSkQBs1j+vvvoqZpZKtoor/JmZGUZGRpidnWVlZYVsNksul0s7\nlogEYKP+6e3t5d577+Xaa6/lscceSyVfxR3SmZ6eJp/PU11dzTXXXEN7e3vakUQkEBv1T6FQ4Lnn\nnqOzs5Njx46lkq/iCl9EZC/r7OzkwQcfTGXZiRa+mX3QzJ42szNmdiTJZa1qbW1ldHSUpaUlFhcX\nGR8f343Fiois2z/f+ta3zs/zhS98gYaGhlTyJXYM38zeAHweaAOeB54wszF3/2ZSywTIZrN0dHTQ\n1NREJpOhpaUFgIcffpg777yT73znOxw6dIgDBw7w6KOPJhlFRAKzXv8cOXKEp59+mn379nHjjTcy\nMDCQSr4k9/DfDZxx92fd/f8BI8A/THB55/X29vLMM89w6tQp6uvrAcjn8zz//PMsLy/z0ksvqexF\nJBFr9c+DDz7I/Pw8c3NzjI+Pc8MNN6SSLcnCvwF47oLHz0fPiYhICszdkxnY7MPAB939X0aPfwF4\nj7t3XTLfYeBw9PBm4OlEAsV3PfDyHh+zHDImMaYy7s3xymXMcsi4HTe6+/44MyZ5Hv4LQM0Fj98a\nPXcRdz8OHE8wx5aY2Wl3b97LY5ZDxiTGVMa9OV65jFkOGZOW5CGdJ4C3m9lNZnY58BFgLMHliYjI\nBhLbw3f3FTPrAh4F3gAMuvs3klqeiIhsLNFLK7j7I8AjSS4jAUkcXir1mOWQMYkxlXFvjlcuY5ZD\nxkQl9qGtiIjsLbq0gohIIFT4sueZWZ2Zze/V8ZIasxxo25QXFb6ISCBU+Akys1EzmzGzb0RfMAti\nzCQyAlVmdp+ZPWVmJ8yseo+NV/Ixy2FbR4LbNmXL3XVL6Aa8Ofp7JTAP/J0QxkxgvDrAgVujx4NA\n914ZL8Exy2FbB7ltyvWmPfxk/aqZPQn8KcVvHb89kDGTyPicu//P6P4fAe/bY+MlMWY5bGsIc9uU\npYr7icO9wsxuA34OeK+7/62ZPQ5cUeljJpExcun5wzs9n7jU45V0zHLY1hcIatuUM+3hJ+da4G+i\nN1YDcDCQMZPICFBrZu+N7n8UOLXHxiv1mOWwrVeFtm3Klgo/OZMUPyh6Crib4j+hQxgziYxQvIrq\nr0Tjvgn4gz02XqnHLIdtvSq0bVO29E1bEZFAaA9fRCQQKnwRkUCo8EVEAqHCFxEJhApfRCQQKnwp\nS2b2vxIYs87MPrrF1/zrTaY/YmbX7SyZSGnotEyRSPRN1G53v2MLr3nF3a9a43mj+P76QQkjiuyI\n9vClLJnZK9Hf28zs8egKiH8RXRHRomlnzazfzP7czL5mZj8ZPT9kZh++dCyKX0b6aTObNbNfu2R5\nbzGzL0fT5s3sp83sbuDK6Ln7on8hPG1m91K8MFlNlOH6aNpTZnZPdKXKL5nZldHYLWY2F43zOdO1\n2yUhKnypBO8CPgG8A3gbcOsF077r7j8FHAN+Z5NxjgDT7n7A3f/DJdM+Cjzq7geAJmDW3Y8AS9H8\nndF8bwd+391vcfdzl4zxduDz7n4LsAD84+j5/wJ8PBr79Zj/m0W2TIUvleBr7v58dPhkluLlcFf9\n8QV/33vpC7fgCeAXzawP+Cl3X1xnvnPuvt4lC/6Pu89G92eAuuj4/tXu/pXo+ft3kFFkQyp8qQTL\nF9x/nYuvAutr3F8h+v++me0DLt9sAe7+ZaAVeAEYMrN/vs6sr24zp0jiVPhS6Tou+Lu6F30WyEX3\n24HLovuLwNVrDWJmNwIvufs9wH8GstGk18zssrVeE4e7LwCLZvae6KmPbHcskc2o8KXSvcnM5oC7\ngNUPYu8B/l70QyDv5Yd75XPA62b25KUf2gK3AU+a2Z9R/I/H70bPHwfmzOy+HWT8GHCPmc0CbwS+\nu4OxRNal0zKlYpnZWaDZ3V9OO8tGzOwqd1896+gI8BZ3vyvlWFKBdAxRJH2HzOxTFN+P54B/kW4c\nqVTawxcRCYSO4YuIBEKFLyISCBW+iEggVPgiIoFQ4YuIBEKFLyISiP8PbOGDcR1FNLkAAAAASUVO\nRK5CYII=\n", "text/plain": [ "" ] }, "metadata": {}, "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", "Let's think about how a CFG would generate this string, working from the top down. The key idea is that every nonterminal symbol covers a substring that is read by a sub-run of the PDA that begins and ends with the _same stack_. The start symbol covers the whole string and corresponds to the whole run. Let's call the start symbol $A_{q_1q_3}$ because the PDA begins in state $q_1$ and ends in state $q_3$. We can picture it as below:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGIRJREFUeJzt3X90V/Wd5/HnWxIHkB8pm1ALJUS3gPIj0BBbOVgR4w9w\nGNkqLt2m9axnOGQO0x0zs3a02h7UkTkdcGdTF2YgUaZkJ8LBRaBaIYSBWFyBQjrAgFY769qxOtOe\nzo4WEBDT9/7xvaGBkuSGfG9uvvm8Hud8z/f7vfd+P/ftvd5XPtyf5u6IiEj/d1naBYiISO9Q4IuI\nBEKBLyISCAW+iEggFPgiIoFQ4IuIBEKBLyISCAW+iEggFPgiIoHIS7uA9goLC72kpCSRtn91+mwi\n7YqIdGXYwPzE2m5pafmluxfFmbZPBX5JSQkHDx5MpO2dr/08kXZFRLpyy8RPJta2mf007rTapSMi\nEggFvohIIBT4IiKBUOCLiARCgS8iEggFvohIIBT4IiKBUOCLiASiT114JWGqffIx9jU3kZefz6gx\nJTzwRA1Dhg1PuyyRfkc9fEld2YxZ1G1ppnbzbkaPvZr1dU+lXZJIv6QevvSqhjU1NG3dSMGIQoqu\nHMX4SaXcc9+Sc+OvnTqdPTteTLFCkf5LgS+95s1jh2netoXVm3bS2trKkgW3Mn5S6XnTND6/nllz\n56dUoUj/psCXXnO0ZT8zK+YycNBgAGbMvv288Q1rahiQl0fFvLvTKE+k31PgS5/QuHkD+19uYvkz\nz2FmaZcj0i8letDWzN42s38ws0Nmlsx9jyVnTCm/nld3befM6VN8ePIEe5t3AHBgzy42rl3F4yvX\nnev9i0j29UYPf7a7/7IX5iN93LiJpcyaM5+quyooGFHIhMnTAFi57GHOnv2IBxctBDIHbquXLk+z\nVJF+Sbt0pFdVVlVTWVUNQP2qFQCs274vzZJEgpH0efgO7DCzFjNbnPC8RESkE0n38G9w93fNbCTQ\nZGY/dvcftJ8g+kOwGKC4uDjhciQNi+o7OHwzdDYAjR2Njzx9b3m2SxIJUqI9fHd/N3r/BbAZ+NxF\npql193J3Ly8qivUcXhERuQSJBb6ZXWFmQ9s+A7cBR5Oan4iIdC7JXTqfBDZH51TnAc+6+/YE5yci\nIp1ILPDd/S1galLti4hI9+humSIigVDgi4gEQoEvIhIIBb6ISCAU+CIigVDgi4gEQoEvIhIIBb6I\nSCAU+CIigVDgi4gEQoEvIhIIBb6ISCAU+CIigVDgi4gEQoEvIhIIBb6ISCAU+CIigVDgi4gEQoEv\nIhIIBb6ISCAU+CIigVDgi4gEQoEvIhIIBb6ISCAU+CIigchLuwDJLbVPPsa+5iby8vMZNaaEB56o\nYciw4WmX9Vtypc6+Tsuxf1EPX7qlbMYs6rY0U7t5N6PHXs36uqfSLumicqXOvk7LsX9RD1861LCm\nhqatGykYUUjRlaMYP6mUe+5bcm78tVOns2fHiylWmJErdfZ1Wo79nwJfLurNY4dp3raF1Zt20tra\nypIFtzJ+Uul50zQ+v55Zc+enVGFGrtTZ12k5hkGBLxd1tGU/MyvmMnDQYABmzL79vPENa2oYkJdH\nxby70yjvnFyps6/TcgyDAl+6rXHzBva/3MTyZ57DzNIup0O5Umdfp+XYfyR+0NbMBpjZ35uZdv7l\nkCnl1/Pqru2cOX2KD0+eYG/zDgAO7NnFxrWreHzlunO9wTTlSp19nZZjGHqjh38/8DowrBfmJVky\nbmIps+bMp+quCgpGFDJh8jQAVi57mLNnP+LBRQuBzIG86qXLVWeO03IMg7l7co2bfRpYBywD/sTd\n53U2fXl5uR88eDCRWna+9vNE2g1F/aoVDBp8xXlnbcS1qL5n6/Tpe8tjT9uTOuU3tByz65aJn0ys\nbTNrcfdYG0nSu3RqgD8Ffp3wfEREpAuJ7dIxs3nAL9y9xcxu6mS6xcBigOLi4qTKkZg67I0PnQ1A\nY4zeend65Jei038xxKwz6RpzgZZjeJLs4c8E7jSzt4ENwM1m9rcXTuTute5e7u7lRUVFCZYjIhK2\nxALf3b/h7p929xLgS8Aud/9KUvMTEZHO6V46IiKB6JULr9y9GWjujXmJiMjFqYcvIhIIBb6ISCAU\n+CIigVDgi4gEQoEvIhIIBb6ISCAU+CIigVDgi4gEQoEvIhIIBb6ISCAU+CIigVDgi4gEQoEvIhII\nBb6ISCC6DHwzuyfOMBER6dvi9PC/EXOYiIj0YR0+AMXM5gJ3AKPN7Kl2o4YBHyddmIiIZFdnT7x6\nDzgI3Am0tBt+HPjjJIsSEZHs6zDw3f0wcNjMnnX3s71Yk4iIJCDOM20/Z2aPAmOj6Q1wd786ycJE\nRCS74gT+M2R24bQArcmWIyIiSYkT+B+4+7bEKxERkUR1dpZOWfRxt5mtAJ4HzrSNd/cfJVybiIhk\nUWc9/P92wffydp8duDn75YiISFI6O0tndm8WIiIiyepyH76Z/clFBn8AtLj7oeyXJNlU++Rj7Gtu\nIi8/n1FjSnjgiRqGDBuedlk5JxeWo2qUrsS5tUI58AfA6OhVBcwB6szsTxOsTbKgbMYs6rY0U7t5\nN6PHXs36uqe6/pH8llxYjqpRuhLnLJ1PA2XufgLAzJYC3wduJHOq5vLkypPuaFhTQ9PWjRSMKKTo\nylGMn1TKPfctOTf+2qnT2bPjxRQrzA25sBxVo1yKOIE/knZn5wBngU+6+ykzO9PBb6SXvXnsMM3b\ntrB6005aW1tZsuBWxk8qPW+axufXM2vu/JQqzA25sBxVo1yqOIHfAOw3s63R998DnjWzK4DXEqtM\nuuVoy35mVsxl4KDBAMyYfft54xvW1DAgL4+KeXenUV7OyIXlqBrlUnUZ+O7+Z2a2DZgZDfoDdz8Y\nfa5MrDLJmsbNG9j/chPLn3kOM0u7nJyVC8tRNUpnOjxoa2bDovcRwFvA/4xeb0XDOmVmA83sh2Z2\n2MyOmdlj2SpaftuU8ut5ddd2zpw+xYcnT7C3eQcAB/bsYuPaVTy+ct253pZ0LBeWo2qUS9VZD/9Z\nYB6ZA7NOdNO0du9d3TztDHCzu58ws3zgFTPb5u77el62XGjcxFJmzZlP1V0VFIwoZMLkaQCsXPYw\nZ89+xIOLFgKZA2XVS3WcvSO5sBxVo1yqzi68mhe9X3UpDbu7Ayeir/nRyy+lLYmnsqqayqpqAOpX\nrQBg3Xb9fe2uXFiOqlEuRZwLr4zMvvqrov35xcCV7v7DGL8dQOZfCJ8BVrn7/otMsxhYDFBcXNzN\n8sO2qP5gh+PeP/welj+IxgEdTwPw9L3lnY4PRUfLsi8tR9UoPRXnLJ2/An5N5t45f0bmiVebgOu6\n+qG7twLTzKwA2Gxmk9396AXT1AK1AOXl5foXQJYU3KDj6dmQC8tRNUpcca60/by7/yFwGsDd/w24\nvDszcff3gd1krtAVEZEUxAn8s9GuGQcwsyIyPf5OmVlR1LPHzAYBtwI/7kGtIiLSA3F26TwFbAZG\nmtkyYAHwzRi/+xSwLvpjcRmw0d11HbWISEriXHjVYGYtQAWZUzL/g7u/HuN3R4DP9rxEERHJhjg9\nfICfAL9qm97Mit39nxKrSkREsi7OaZn/BVgK/JzMQ8zbLrwq7ex3IiLSt8Tp4d8PTHD3f026GBER\nSU6cs3TeIfOEKxERyWEd9vDbPdrwLaDZzL5Pu/viu/tfJlybiIhkUWe7dIZG7/8UvS6nmxdciYhI\n39HZzdN0O2MRkX4kzj58ERHpBxT4IiKB6DLwL/Z0KzO7pHvki4hIeuL08F9oe9whgJlNBF5IriQR\nEUlCnMD/czKhP8TMpgPPAV9JtiwREcm2ODdP+370TNodZE7V/KK7v5l4ZSIiklWdXXj1Pzj/GbTD\ngf8DfM3McPc/Sro4ERHJns56+Bc+fLIlyUJERCRZnV14tQ7AzK4ATkfPp217MPnv9E55IiKSLXEO\n2v4dMKjd90HAzmTKERGRpMQJ/IHufqLtS/R5cHIliYhIEuIE/kkzK2v7Ep2aeSq5kkREJAlxHoBS\nDTxnZu+RedrVlcDCRKsSEZGsi3Me/gEzuwaYEA16w93PJluWiIhkW9yHmE8AJgIDgbLoPPz65MoS\nEZFsi/MQ86XATWQC/yVgLvAKoMAXEckhcQ7aLgAqgH9x9/uAqWSuuhURkRwSZ5fOKXf/tZl9HN01\n8xfAmITrClLtk4+xr7mJvPx8Ro0p4YEnahgyTH9b+yut7+zQcowvTg//oJkVAHVkbq/wI2BvolUF\nqmzGLOq2NFO7eTejx17N+rqn0i5JEqT1nR1ajvHFOUtnSfRxtZltB4a5+5Fky+r/GtbU0LR1IwUj\nCim6chTjJ5Vyz31Lzo2/dup09ux4McUKJZu0vrNDy7Fn4jzx6u/aPrv72+5+pP0w6b43jx2medsW\nVm/aybLVDbx59NBvTdP4/Hqu+8LNKVQn2ab1nR1ajj3X2e2RB5K5hUKhmX2CzEVXAMOA0b1QW791\ntGU/MyvmMnBQ5g4VM2bfft74hjU1DMjLo2Le3WmUJ1mm9Z0dWo4919kunSoyV9mOIrPvvi3wfwWs\nTLiuYDVu3sD+l5tY/sxzmFnXP5CcpvWdHVqO8XS4S8fdv+PuVwEPuPvV7n5V9Jrq7l0GvpmNMbPd\nZvaamR0zs/uzWnkOm1J+Pa/u2s6Z06f48OQJ9jbvAODAnl1sXLuKx1euO9eLkdyn9Z0dWo49F+e0\nzH8xs6HuftzMvgmUAU+4+4+6+N3HwH919x+Z2VCgxcya3P21nhad68ZNLGXWnPlU3VVBwYhCJkye\nBsDKZQ9z9uxHPLgoc6uia6dOp3rp8jRLlSzQ+s4OLceeixP433L358zsBuAWYAXw18DnO/uRu/8z\n8M/R5+Nm9jqZff/BBz5AZVU1lVXVANSvWgHAuu370ixJEqT1nR1ajj0T5zz81uj9d4Fad/8+cHl3\nZmJmJcBngf3d+Z2IiGRPnB7+u2a2BrgV+Asz+x3i/aEAwMyGAJuAanf/1UXGLwYWAxQXF8dtNict\nqr/wMcGRobMBaOxofOTpe8uzXZIkpMN1DVrf3aTtJnviBPd/BBqB2939fWAE8PU4jZtZPpmwb3D3\n5y82jbvXunu5u5cXFRXFLFtERLorzpW2HwLPt/t+bt98ZyxzbtQzwOvu/pc9KVJERHou9q6ZSzAT\n+Cpws5kdil53JDg/ERHpRNwHoHSbu7/Cby7WEhGRlCXZwxcRkT5EgS8iEggFvohIIBT4IiKBUOCL\niARCgS8iEggFvohIIBT4IiKBUOCLiARCgS8iEggFvohIIBT4IiKBUOCLiARCgS8iEggFvohIIBT4\nIiKBUOCLiARCgS8iEggFvohIIBT4IiKBUOCLiARCgS8iEggFvohIIBT4IiKBUOCLiAQiL+0Cclnt\nk4+xr7mJvPx8Ro0p4YEnahgybHjaZYlID/Tn7Vo9/B4omzGLui3N1G7ezeixV7O+7qm0SxKRHurP\n27V6+DE1rKmhaetGCkYUUnTlKMZPKuWe+5acG3/t1Ons2fFiihWKSHeFtl0r8GN489hhmrdtYfWm\nnbS2trJkwa2Mn1R63jSNz69n1tz5KVUoIt0V4natwI/haMt+ZlbMZeCgwQDMmH37eeMb1tQwIC+P\ninl3p1GeiFyCELdrBX4PNW7ewP6Xm1j+zHOYWdrliEgW9NftOrGDtma21sx+YWZHk5pHb5lSfj2v\n7trOmdOn+PDkCfY27wDgwJ5dbFy7isdXrjvXSxCR3BDidp1kD/+7wEqgPsF59IpxE0uZNWc+VXdV\nUDCikAmTpwGwctnDnD37EQ8uWghkDvBUL12eZqkiElOI23Vige/uPzCzkqTa722VVdVUVlUDUL9q\nBQDrtu9LsyQR6aHQtuvU9+Gb2WJgMUBxcXHK1fzGovqDHY57//B7WP4gGgd0PA3A0/eWZ7ssEemh\njrbtuNs15O62nXrgu3stUAtQXl7uKZcTS8ENlWmXICJZFsJ2rSttRUQCocAXEQlEkqdlrgf2AhPM\n7Gdm9vtJzUtERLqW5Fk6/ymptkVEpPu0S0dEJBAKfBGRQCjwRUQCocAXEQmEAl9EJBAKfBGRQCjw\nRUQCocAXEQmEAl9EJBAKfBGRQCjwRUQCocAXEQmEAl9EJBAKfBGRQCjwRUQCocAXEQmEAl9EJBAK\nfBGRQCjwRUQCocAXEQmEAl9EJBAKfBGRQCjwRUQCocAXEQlEMIH/cuP3WHTnjdw2+VO8cfRQ2uWI\nSEC+9a1vUVpayrRp07jtttt47733UqkjmMAv+cw1LP3OWqaUX592KSISmK9//escOXKEQ4cOMW/e\nPB5//PFU6shLZa4JW7ZsGevWrWPkyJGMGTOG6dOnM+2Or6ZdlogEoGFNDU1bN1IwopCiK0cxflIp\nt6x47Nz4kydPYmap1NbvAr+lpYUNGzZw6NAhPv74Y8rKypg+fXraZYlIAN48dpjmbVtYvWknra2t\nLFlwK+MnlQLwyCOPUF9fz/Dhw9m9e3cq9fW7XTp79uzhi1/8IoMHD2bYsGHceeedaZckIoE42rKf\nmRVzGThoMFcMGcqM2befG7ds2TLeeecdKisrWblyZSr19bvAFxHpyyorK9m0aVMq80408M1sjpm9\nYWb/aGYPJTmvNjfeeCNbtmzh1KlTHD9+nBdeeKE3ZisiwpTy63l113bOnD7FhydPsLd5BwA/+clP\nzk2zdetWrrnmmlTqS2wfvpkNAFYBtwI/Aw6Y2ffc/bWk5glQVlbGwoULmTp1KiNHjuS6664D4JWd\nL7Hqzx/hg//3r3xzyVf49xMm8+26DUmWIiKBGTexlFlz5lN1VwUFIwqZMHkaAA899BBvvPEGl112\nGWPHjmX16tWp1JfkQdvPAf/o7m8BmNkGYD6QaOBD5uDII488AsCjjz4KwA233MENt9yR9KxFJHCV\nVdVUVlUDUL9qBUBqu3AulOQundHAO+2+/ywaJiIiKTB3T6ZhswXAHHdfFH3/KvB5d//aBdMtBhZH\nXycAbyRSUHyFwC/7eJu5UGMSbarGvtlerrSZCzVeirHuXhRnwiR36bwLjGn3/dPRsPO4ey1Qm2Ad\n3WJmB929vC+3mQs1JtGmauyb7eVKm7lQY9KS3KVzABhnZleZ2eXAl4DvJTg/ERHpRGI9fHf/2My+\nBjQCA4C17n4sqfmJiEjnEr21gru/BLyU5DwSkMTupWy3mQs1JtGmauyb7eVKm7lQY6ISO2grIiJ9\ni26tICISCAW+9HlmVmJmR/tqe0m1mQu0bnKLAl9EJBAK/ASZ2RYzazGzY9EFZkG0mUSNQJ6ZNZjZ\n62b2v8xscB9rL+tt5sK6jgS3bnKWu+uV0AsYEb0PAo4C/y6ENhNorwRwYGb0fS3wQF9pL8E2c2Fd\nB7lucvWlHn6y/sjMDgP7yFx1PC6QNpOo8R13/9/R578Fbuhj7SXRZi6sawhz3eSkfveIw77CzG4C\nbgFmuPuHZtYMDOzvbSZRY+TC84d7ej5xttvLapu5sK7bCWrd5DL18JMzHPi3aMO6Brg+kDaTqBGg\n2MxmRJ+/DLzSx9rLdpu5sK7bhLZucpYCPznbyRwoeh34Npl/QofQZhI1QuYuqn8YtfsJ4K/7WHvZ\nbjMX1nWb0NZNztKVtiIigVAPX0QkEAp8EZFAKPBFRAKhwBcRCYQCX0QkEAp8yUlm9moCbZaY2Ze7\n+ZuHuxj/kpkV9KwykezQaZkikehK1AfcfV43fnPC3YdcZLiR2b5+ncUSRXpEPXzJSWZ2Inq/ycya\nozsg/ji6I6JF4942s+Vm9g9m9kMz+0w0/LtmtuDCtshcjPQFMztkZn98wfw+ZWY/iMYdNbMvmNm3\ngUHRsIboXwhvmFk9mRuTjYlqKIzGvW5mddGdKneY2aCo7evM7EjUzgrTvdslIQp86Q8+C1QDE4Gr\ngZntxn3g7lOAlUBNF+08BOxx92nu/t8vGPdloNHdpwFTgUPu/hBwKpq+MppuHPBX7j7J3X96QRvj\ngFXuPgl4H7g7Gv43QFXUdmvM/2aRblPgS3/wQ3f/WbT75BCZ2+G2Wd/ufcaFP+yGA8B9ZvYoMMXd\nj3cw3U/dvaNbFvxfdz8UfW4BSqL9+0PdfW80/Nke1CjSKQW+9Adn2n1u5fy7wPpFPn9M9P++mV0G\nXN7VDNz9B8CNwLvAd83s3g4mPXmJdYokToEv/d3Cdu9tvei3genR5zuB/OjzcWDoxRoxs7HAz929\nDngaKItGnTWz/Iv9Jg53fx84bmafjwZ96VLbEumKAl/6u0+Y2RHgfqDtQGwdMCt6EMgMftMrPwK0\nmtnhCw/aAjcBh83s78n88fhONLwWOGJmDT2o8feBOjM7BFwBfNCDtkQ6pNMypd8ys7eBcnf/Zdq1\ndMbMhrh721lHDwGfcvf7Uy5L+iHtQxRJ3++a2TfIbI8/Bf5zuuVIf6UevohIILQPX0QkEAp8EZFA\nKPBFRAKhwBcRCYQCX0QkEAp8EZFA/H/0W1WVn6VrRAAAAABJRU5ErkJggg==\n", "text/plain": [ "" ] }, "metadata": {}, "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": 10, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGbJJREFUeJzt3X10VfWd7/H3FwJDNAIVYq1ACL1GuBAJjbFVdEBErDI+\n3FbupZZ21ihdwHK8PtHOpdousQwuR2e8tsIYw/g8irYiKD4RwcTCaFOSTsQIPl21gzrTrk5HKwoI\n+L1/nB0MSMIO2Ts7J7/Pa62zzjl77/PbH/f2fPnld/aDuTsiItL79ck6gIiIdA8VfBGRQKjgi4gE\nQgVfRCQQKvgiIoFQwRcRCYQKvohIIFTwRUQCoYIvIhKIgqwDtDV06FAvLS1Npe0/7diVeJvbP9mT\neJsikq3C/n0Tb3PggH6Jt9mqqanpD+5eHGfZHlXwS0tLaWxsTKXttZt/l3ibzVvfT7xNEcnWhBGD\nE2/zjLFfTLzNVmb227jLakhHRCQQKvgiIoFQwRcRCYQKvohIIFTwRUQCoYIvIhIIFXwRkUCo4IuI\nBKJHnXglYXp82Y1sbqijb0E/hhxTwsyrrqewaGDWsUR6HfXwJXNllROZf/tq5lc/RvGwUp59qCbr\nSCK9knr40q3WLa+mce1KigYNYXDx0QwrG8dpM2bvnV8ypoKXNqzJMKFI76UevnSbd15vofm5J7hy\n6SpmL6ph62stn1tmY+0KRldNyiCdSO+nHr50m7damiifOI3+AwoBGHvSlH3mr1teTZ++BVSefm4W\n8UR6PRV86RE21j7C5oY65t5wN2aWdRyRXinVIR0ze9vMXjKzZjNL57rHkjdGlVfR8vxadu3cwY6P\nt7GloR6AVxrXU//wHVy08La9vX8RSV539PCnuPsfumE90sMNLxvHhMnTufmS8ykaNIThx5UDsGrp\nInbv+oSaqy8GYOSYCi647Loso4r0ShrSkW419cJ5TL1wHgC1990KwIK7arOMJBKMtI/ScaDWzJrM\nbE7K6xIRkQ6k3cM/1d3fNbOjgGfM7BV3/2XbBaJ/COYAlJSUpBxHsrCk7o0Dzxh+NgAt7c2PXDrl\n2KQjiQQp1R6+u78bPf8eWAl89QDL1Lh7lbtXFRfHug+viIgcgtQKvpkdbmZHtL4GzgQ+f6aNiIh0\nizSHdL4IrIyOqS4AHnD3p1Ncn4iIdCC1gu/ubwIVabUvIiKdo2vpiIgEQgVfRCQQKvgiIoFQwRcR\nCYQKvohIIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGC\nLyISCBV8EZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGRQKjgi4gE\noiDrAJJfHl92I5sb6uhb0I8hx5Qw86rrKSwamHWsz8mXnD2dtmPvoh6+dEpZ5UTm376a+dWPUTys\nlGcfqsk60gHlS86eTtuxd1EPX9q1bnk1jWtXUjRoCIOLj2ZY2ThOmzF77/ySMRW8tGFNhglz8iVn\nT6ft2Puphy8H9M7rLTQ/9wRXLl3F7EU1bH2t5XPLbKxdweiqSRmk+0y+5OzptB3DoB6+HNBbLU2U\nT5xG/wGFAIw9aco+89ctr6ZP3wIqTz83i3h75UvOnk7bMQwq+NJpG2sfYXNDHXNvuBszyzpOu/Il\nZ0+n7dh7pD6kY2Z9zexfzezxtNclyRlVXkXL82vZtXMHOz7expaGegBeaVxP/cN3cNHC2/b2BrOU\nLzl7Om3HMHRHD/9yYAugY7nyyPCycUyYPJ2bLzmfokFDGH5cOQCrli5i965PqLn6YgBGjqnggsuu\nU848p+0YBnP39Bo3Gw7cAywGrnL3czpavqqqyhsbG1PJsnbz7xJvs3nr+4m32VPV3ncr/QsP2+eo\njbiW1L3RpXVfOuXY2Mt2Jad8JuTtOGHE4MTbPGPsFxNvs5WZNbl7VZxl0x7SuQX4G+DTlNcjIiIH\nkdqQjpmdA/ze3ZvM7LQOlpsDzAEoKSlJK47E1G5vfPjZALTE6K13pkd+KDr8iyFmzrQz5gNtx/Ck\n2cM/BTjPzN4GHgRON7N/3n8hd69x9yp3ryouLk4xjohI2FIr+O7+Q3cf7u6lwLeAZ939O2mtT0RE\nOqYzbUVEAtEtJ165ez1Q3x3rEhGRA1MPX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8\nEZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEoiDFnwz+59xpomISM8Wp4f/\nw5jTRESkB2v3BihmdjYwHRhmZj9rM2sgsDvtYCIikqyO7nj1HtAInAc0tZn+IXBlmqFERCR57RZ8\nd38ReNHMHnD3Xd2YSUREUhDnnrZfNbOFwMhoeQPc3b+cZjAREUlWnIJ/B7khnCZgT7pxREQkLXEK\n/gfu/lTqSUREJFUdHaVTGb2sM7ObgEeAna3z3f03KWcTEZEEddTD/4f93le1ee3A6cnHERGRtHR0\nlM6U7gwiIiLpOugYvplddYDJHwBN7t6cfCRJ0uPLbmRzQx19C/ox5JgSZl51PYVFA7OOlXfyYTsq\noxxMnEsrVAHzgGHRYy5wFrDMzP4mxWySgLLKicy/fTXzqx+jeFgpzz5Uk3WkvJQP21EZ5WDiHKUz\nHKh0920AZnYt8AQwidyhmjemF086Y93yahrXrqRo0BAGFx/NsLJxnDZj9t75JWMqeGnDmgwT5od8\n2I7KKIciTg//KNocnQPsAr7o7tv3my4Zeuf1Fpqfe4Irl65i9qIatr7W8rllNtauYHTVpAzS5Y98\n2I7KKIcqTg//fqDBzB6N3p8LPGBmhwObU0smnfJWSxPlE6fRf0AhAGNP2vc393XLq+nTt4DK08/N\nIl7eyIftqIxyqA5a8N19kZk9BZwSTZrn7o3R61mpJZPEbKx9hM0Ndcy94W7MLOs4eSsftqMySkfa\nHdIxs4HR85HAm8B90ePNaFqHzGyAmf3azF40s5fN7LqkQsvnjSqvouX5tezauYMdH29jS0M9AK80\nrqf+4Tu4aOFte3tb0r582I7KKIeqox7+A8A55H6YdaKLprV5PtjF03YCp7v7NjPrB2wws6fc/Vdd\njy37G142jgmTp3PzJedTNGgIw48rB2DV0kXs3vUJNVdfDMDIMRVccJn+7W1PPmxHZZRD1dGJV+dE\nz6MOpWF3d2Bb9LZf9PBDaUvimXrhPKZeOA+A2vtuBWDBXbVZRspL+bAdlVEORZwTr4zcWP2oaDy/\nBDja3X8d47N9yf2FcCyw1N0bDrDMHGAOQElJSSfjh21J3Rvtznv/7T9i/bbT0sEyAJdOOTbpWHmp\nvW3Zk7ajMkpXxTlK5x+BT8ldO2cRuTterQBOPNgH3X0PMMHMBgMrzazc3Vv2W6YGqAGoqqrSXwAJ\nGXyqfk9PQj5sR2WUuOIch/81d/9rYAeAu/8X0L8zK3H394E6cmfoiohIBuIU/F3R0IwDmFkxuR5/\nh8ysOOrZY2aFwDTglS5kFRGRLogzpPMzYCVwlJktBmYAP4rxuS8B90T/WPQBfu7ujx9yUhER6ZI4\nJ17db2ZNwFRyh2T+D3ffEuNzm4CvdD2iiIgkIU4PH+B14E+ty5tZibv/W2qpREQkcXEOy/zfwLXA\n78jdxLz1xKvx6UYTEZEkxenhXw6Mdvf/TDuMiIikJ85ROlvJ3eFKRETyWLs9/Da3NnwTqDezJ2hz\n/Xt3vznlbCIikqCOhnSOiJ7/LXr0p5MnXImISM/R0cXTdAk7EZFeJM4YvoiI9AIq+CIigThowT/Q\n3a3M7JCukS8iItmJ08Nf3Xq7QwAzGwusTi+SiIikIU7Bv55c0S8ysxOAXwDfSTeWiIgkLc7F056I\n7klbS+5QzW+4+2upJxMRkUR1dOLVrex7D9pBwP8DLjUz3P2ytMOJiEhyOurhN+73vinNICIikq6O\nTry6B8DMDgd2RPenbb0x+Z91TzwREUlKnB9t1wGFbd4XAmvTiSMiImmJU/AHuPu21jfR68PSiyQi\nImmIU/A/MrPK1jfRoZnb04skIiJpiHMDlCuAX5jZe+TudnU0MDPVVCIikrg4x+FvNLMxwOho0qvu\nvivdWCIikrS4NzEfDYwFBgCV0XH496YXS0REkhbnJubXAqeRK/hPAmcDGwAVfBGRPBLnR9sZwFTg\nP9z9IqCC3Fm3IiKSR+IM6Wx390/NbHd01czfAyNSzhWkx5fdyOaGOvoW9GPIMSXMvOp6CosGHvyD\nkpe0v5Oh7RhfnB5+o5kNBpaRu7zCb4AXUk0VqLLKicy/fTXzqx+jeFgpzz5Uk3UkSZH2dzK0HeOL\nc5TOJdHLajN7Ghjo7pvSjdX7rVteTePalRQNGsLg4qMZVjaO02bM3ju/ZEwFL21Yk2FCSZL2dzK0\nHbsmzh2v1rW+dve33X1T22nSee+83kLzc09w5dJVzF5Uw9bXWj63zMbaFYyumpRBOkma9ncytB27\nrqPLIw8gdwmFoWb2BXInXQEMBIZ1Q7Ze662WJsonTqP/gNwlisaeNGWf+euWV9OnbwGVp5+bRTxJ\nmPZ3MrQdu66jIZ255M6yPYbc2H1rwf8TsCTlXMHaWPsImxvqmHvD3ZjZwT8geU37OxnajvG0O6Tj\n7j9191HA9939y+4+KnpUuPtBC76ZjTCzOjPbbGYvm9nliSbPY6PKq2h5fi27du5gx8fb2NJQD8Ar\njeupf/gOLlp4295ejOQ/7e9kaDt2XZzDMv/DzI5w9w/N7EdAJfC37v6bg3xuNzDf3X9jZkcATWb2\njLtv7mrofDe8bBwTJk/n5kvOp2jQEIYfVw7AqqWL2L3rE2quvhiAkWMquOCy67KMKgnQ/k6GtmPX\nxSn4P3b3X5jZqcAZwE3AbcDXOvqQu/878O/R6w/NbAu5sf/gCz7A1AvnMfXCeQDU3ncrAAvuqs0y\nkqRI+zsZ2o5dE+c4/D3R818ANe7+BNC/Mysxs1LgK0BDZz4nIiLJidPDf9fMbgemAX9nZn9GvH8o\nADCzImAFcIW7/+kA8+cAcwBKSkriNpuXltS9ceAZw88GoKW9+ZFLpxybdCRJSbv7GrS/O0nfm+TE\nKdz/C1gDfN3d3weOBH4Qp3Ez60eu2N/v7o8caBl3r3H3KnevKi4ujhlbREQ6K86Zth8Dj7R5v3ds\nviOWOzbqDmCLu9/clZAiItJ1sYdmDsEpwHeB082sOXpMT3F9IiLSgbg3QOk0d9/AZydriYhIxtLs\n4YuISA+igi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCYQKvohIIFTwRUQCoYIvIhIIFXwR\nkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8EZFAqOCLiARCBV9EJBAq\n+CIigVDBFxEJhAq+iEggVPBFRAJRkHWAfPb4shvZ3FBH34J+DDmmhJlXXU9h0cCsY4lIF9T8/XX8\nqv4ZCvr145gRpXz/b2+haOCgrGMlQj38LiirnMj821czv/oxioeV8uxDNVlHEpEuqjx5MstW1VOz\nso5hI7/M8mU/yzpSYtTDj+n+22/hmUd/zuAjh1J89DEcN248o8/49t75JWMqeGnDmgwTikhnrVte\nTePalRQNGsLg4qMZVjaOK66cv3f+f684gfW1j2eYMFkq+DG89vKL1D+1iuoVa9mzZw+XzJjGcePG\n77PMxtoVVEyanlFCEemsd15vofm5J7hy6So+3bOHWy79JsPKxu2zzJpHljP57PMzSpg8FfwYWpoa\nOGXq2QwoPAyAk6d8fZ/565ZX06dvAZWnn5tFPBE5BG+1NFE+cRr9BxQCMPakKfvMv//2W+hbUMDU\ncy7IIl4qVPC7aGPtI2xuqGPuDXdjZlnHEZEErFn5IA3PPcONd/yiV32vU/vR1szuNLPfm1lLWuvo\nLsdXncTzzz7Nzh3b+fijbbxQXwvAK43rqX/4Di5aeNveXoKI5IdR5VW0PL+WXTt3sOPjbWxpqAdg\n4/pn+fmdS/nJknv2/lXfW6TZw78bWALcm+I6ukXZ2PFMPut85n5zKoOPHMro8gkArFq6iN27PqHm\n6osBGDmmggsuuy7LqCIS0/CycUyYPJ2bLzmfokFDGH5cOQBLFl/Nrl2f8H++NxPI/XB7xbU3Zhk1\nMakVfHf/pZmVptV+d5s19wpmzb0CgHuX3gTAgrtqs4wkIl009cJ5TL1wHgC1990KwD1P/yrLSKnK\nfAzfzOYAcwBKSkoyTvOZ793b2O689198D+tXyKC+b3TYxj/9ZVWimSaMGJxoe/nSpjL2zPbSaLM7\nMrb33X7/7T9i/bbT0sF3v1XS3+3uknnBd/caoAagqqrKM44Ty+BTZ2UdQUQSFsL3WmfaiogEQgVf\nRCQQaR6WuRx4ARhtZu+Y2ey01iUiIgeX5lE6F6bVtoiIdJ6GdEREAqGCLyISCBV8EZFAqOCLiARC\nBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcR\nCYQKvohIIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCCCKfjPrXmM\n7503iTPLv8SrLc1ZxxGRgPz4xz9m/PjxTJgwgTPPPJP33nsvkxzBFPzSY8dw7U/v5Piqk7KOIiKB\n+cEPfsCmTZtobm7mnHPO4Sc/+UkmOQoyWWvKFi9ezD333MNRRx3FiBEjOOGEE5gw/btZxxKRANx/\n+y088+jPGXzkUIqPPobjxo3njJuu2zv/o48+wswyydbrCn5TUxMPPvggzc3N7N69m8rKSk444YSs\nY4lIAF57+UXqn1pF9Yq17Nmzh0tmTOO4ceMBuOaaa7j33nsZNGgQdXV1meTrdUM669ev5xvf+AaH\nHXYYAwcO5Lzzzss6kogEoqWpgVOmns2AwsM4vOgITp7y9b3zFi9ezNatW5k1axZLlizJJF+vK/gi\nIj3ZrFmzWLFiRSbrTrXgm9lZZvaqmb1hZgvSXFerSZMmsWrVKrZv386HH37I6tWru2O1IiIcX3US\nzz/7NDt3bOfjj7bxQn0tAK+//vreZR599FHGjBmTSb7UxvDNrC+wFJgGvANsNLPH3H1zWusEqKys\nZObMmVRUVHDUUUdx4oknArBh7ZMsvf4aPvjjf/KjS77Dfxtdzg3LHkwziogEpmzseCafdT5zvzmV\nwUcOZXT5BAAWLFjAq6++Sp8+fRg5ciTV1dWZ5EvzR9uvAm+4+5sAZvYgcD6QasGH3I8j11xzDQAL\nFy4E4NQzpnPqGdPTXrWIBG7W3CuYNfcKAO5dehNAZkM4+0tzSGcYsLXN+3eiaSIikgFz93QaNpsB\nnOXu34vefxf4mrtfut9yc4A50dvRwKupBIpvKPCHHt5mPmRMo01l7Jnt5Uub+ZDxUIx09+I4C6Y5\npPMuMKLN++HRtH24ew1Qk2KOTjGzRnev6slt5kPGNNpUxp7ZXr60mQ8Z05bmkM5GoMzMRplZf+Bb\nwGMprk9ERDqQWg/f3Xeb2aXAGqAvcKe7v5zW+kREpGOpXlrB3Z8EnkxzHSlIY3gp6TbzIWMabSpj\nz2wvX9rMh4ypSu1HWxER6Vl0aQURkUCo4EuPZ2alZtbSU9tLq818oH2TX1TwRUQCoYKfIjNbZWZN\nZvZydIJZEG2mkREoMLP7zWyLmT1sZof1sPYSbzMf9nUkuH2Tt9xdj5QewJHRcyHQAgwJoc0U2isF\nHDglen8n8P2e0l6KbebDvg5y3+TrQz38dF1mZi8CvyJ31nFZIG2mkXGru/9L9PqfgVN7WHtptJkP\n+xrC3Dd5qdfd4rCnMLPTgDOAk939YzOrBwb09jbTyBjZ//jhrh5PnHR7ibaZD/u6jaD2TT5TDz89\ng4D/ir5YY4CTAmkzjYwAJWZ2cvT628CGHtZe0m3mw75uFdq+yVsq+Ol5mtwPRVuAG8j9CR1Cm2lk\nhNxVVP86avcLwG09rL2k28yHfd0qtH2Tt3SmrYhIINTDFxEJhAq+iEggVPBFRAKhgi8iEggVfBGR\nQKjgS14ys+dTaLPUzL7dyc9cfZD5T5rZ4K4lE0mGDssUiURnon7f3c/pxGe2uXvRAaYbue/XpwlG\nFOkS9fAlL5nZtuj5NDOrj66A+Ep0RUSL5r1tZjea2Utm9mszOzaafreZzdi/LXInI/25mTWb2ZX7\nre9LZvbLaF6Lmf25md0AFEbT7o/+QnjVzO4ld2GyEVGGodG8LWa2LLpSZa2ZFUZtn2hmm6J2bjJd\nu11SooIvvcFXgCuAscCXgVPazPvA3Y8HlgC3HKSdBcB6d5/g7v93v3nfBta4+wSgAmh29wXA9mj5\nWdFyZcA/uvs4d//tfm2UAUvdfRzwPnBBNP0uYG7U9p6Y/80inaaCL73Br939nWj4pJnc5XBbLW/z\nfPL+H+yEjcBFZrYQON7dP2xnud+6e3uXLHjL3Zuj101AaTS+f4S7vxBNf6ALGUU6pIIvvcHONq/3\nsO9VYP0Ar3cT/b9vZn2A/gdbgbv/EpgEvAvcbWZ/2c6iHx1iTpHUqeBLbzezzXNrL/pt4ITo9XlA\nv+j1h8ARB2rEzEYCv3P3ZcA/AZXRrF1m1u9An4nD3d8HPjSzr0WTvnWobYkcjAq+9HZfMLNNwOVA\n6w+xy4DJ0Y1ATuazXvkmYI+Zvbj/j7bAacCLZvav5P7x+Gk0vQbYZGb3dyHjbGCZmTUDhwMfdKEt\nkXbpsEzptczsbaDK3f+QdZaOmFmRu7cedbQA+JK7X55xLOmFNIYokr2/MLMfkvs+/hb4q2zjSG+l\nHr6ISCA0hi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCcT/B9u5YFuCHDJlAAAAAElFTkSu\nQmCC\n", "text/plain": [ "" ] }, "metadata": {}, "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 that begins and ends with the same stack 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": 11, "metadata": { "scrolled": true }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGohJREFUeJzt3X10VfWd7/H3FwJDLEIqBK1AiFYeCtTQEFt8KIhI6wPq\nZfReapnOupYucDlWUXSGynT5QLFenOt1KowhjAo6CFV5ULBCBBMLV01JOhEjKHrVDuiMrfeOLSgg\n0O/942xiwDyckLOzc/L7vNY665yz9z6//XFvz5dffmc/mLsjIiKdX5ekA4iISPtQwRcRCYQKvohI\nIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKByEk6QEN9+/b1wsLCpGOk7U/7D2a0vX2f\nHc5oeyIhyO3eNaPt9erRLaPtxa2mpuYjd89PZ9kOVfALCwuprq5OOkbaNm7/MKPt1e76OKPtiYRg\n1MC8jLZ34fCTM9pe3Mzsd+kuqyEdEZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKh\ngi8iEogOdeKVhGnd4vlsr6qga043+pxawJSb7ya3Z6+kY4l0OurhS+IGF5/DrEVrmVX6DPn9C3nh\nl2VJRxLplNTDl3a1aXkp1RtX07N3H/LyT6H/4BGcf9W0+vkFw4p4bcuGBBOKdF7q4Uu72f1WHbUv\nPstNC9cwbW4Zu3bWfWGZreUrGVoyNoF0Ip2fevjSbt6tq2HkORPp3iMXgOFjxh81f9PyUrp0zaH4\ngsuSiCfS6angS4ewtXwV26sqmHHPEsws6TginVKsQzpm9p6ZvWZmtWaWPdc9llicNrKEupc2cvDA\nfvZ/upcdVZUAvFG9mcqnHuKaOx6s7/2LSOa1Rw9/vLt/1A7rkQ5uwOARjBp3CfdddwU9e/dhwJCR\nAKxZOJdDBz+j7LYfAjBoWBFX3nBnklFFOiUN6Ui7mnD1tUy4+loAyh97AIDZj5QnGUkkGHEfpeNA\nuZnVmNn0mNclIiLNiLuHf567v29m/YDnzewNd/91wwWifwimAxQUFMQcR5KwoOLtxmcMuBiAuqbm\nR64ff0amI4kEKdYevru/Hz3/HlgNfLORZcrcvcTdS/Lz07oPr4iIHIfYCr6ZfcnMTjzyGvgO8MUz\nbUREpF3EOaRzMrA6OqY6B3jc3dfHuD4REWlGbAXf3d8BiuJqX0REWkfX0hERCYQKvohIIFTwRUQC\noYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8EZFAqOCL\niARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQ\nwRcRCURO0gEku6xbPJ/tVRV0zelGn1MLmHLz3eT27JV0rC/IlpwdnbZj56IevrTK4OJzmLVoLbNK\nnyG/fyEv/LIs6UiNypacHZ22Y+eiHr40adPyUqo3rqZn7z7k5Z9C/8EjOP+qafXzC4YV8dqWDQkm\nTMmWnB2dtmPnpx6+NGr3W3XUvvgsNy1cw7S5ZezaWfeFZbaWr2RoydgE0n0uW3J2dNqOYVAPXxr1\nbl0NI8+ZSPceuQAMHzP+qPmblpfSpWsOxRdclkS8etmSs6PTdgyDCr602tbyVWyvqmDGPUsws6Tj\nNClbcnZ02o6dR+xDOmbW1cz+1czWxb0uyZzTRpZQ99JGDh7Yz/5P97KjqhKAN6o3U/nUQ1xzx4P1\nvcEkZUvOjk7bMQzt0cO/EdgB6FiuLDJg8AhGjbuE+667gp69+zBgyEgA1iycy6GDn1F22w8BGDSs\niCtvuFM5s5y2YxjM3eNr3GwAsBSYB9zs7pOaW76kpMSrq6tjy5NpG7d/mNH2and9nNH2Mqn8sQfo\nnnvCUUdtpGtBxdttWvf1489Ie9m25JTPZdN2HDUwL6PtXTj85Iy2Fzczq3H3knSWjXtI537gb4E/\nx7weERFpQWxDOmY2Cfi9u9eY2fnNLDcdmA5QUFAQVxxJU5O98QEXA1CXRm+9NT3y49HsXwxp5ow7\nYzbQdgxPnD38c4HLzew9YAVwgZn9y7ELuXuZu5e4e0l+fn6McUREwhZbwXf3n7j7AHcvBL4HvODu\nfxXX+kREpHk601ZEJBDtcuKVu1cCle2xLhERaZx6+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggV\nfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCYQKvohIIFTwRUQCoYIvIhIIFXwRkUC0WPDN7L+mM01E\nRDq2dHr4P0lzmoiIdGBN3gDFzC4GLgH6m9kvGszqBRyKO5iIiGRWc3e8+gCoBi4HahpM3wPcFGco\nERHJvCYLvru/CrxqZo+7+8F2zCQiIjFI55623zSzO4BB0fIGuLufHmcwERHJrHQK/kOkhnBqgMPx\nxhERkbikU/D/6O7PxZ5ERERi1dxROsXRywozuxdYBRw4Mt/dfxtzNhERyaDmevj/85j3JQ1eO3BB\n5uOIiEhcmjtKZ3x7BhERkXi1OIZvZjc3MvmPQI2712Y+kmTSusXz2V5VQdecbvQ5tYApN99Nbs9e\nScfKOtmwHZVRWpLOpRVKgGuB/tFjBnARsNjM/jbGbJIBg4vPYdaitcwqfYb8/oW88MuypCNlpWzY\njsooLUnnKJ0BQLG77wUws9uBZ4GxpA7VnB9fPGmNTctLqd64mp69+5CXfwr9B4/g/Kum1c8vGFbE\na1s2JJgwO2TDdlRGOR7p9PD70eDoHOAgcLK77ztmuiRo91t11L74LDctXMO0uWXs2ln3hWW2lq9k\naMnYBNJlj2zYjsooxyudHv4yoMrMno7eXwY8bmZfArbHlkxa5d26GkaeM5HuPXIBGD7m6N/cNy0v\npUvXHIovuCyJeFkjG7ajMsrxarHgu/tcM3sOODeadK27V0evp8aWTDJma/kqtldVMOOeJZhZ0nGy\nVjZsR2WU5jQ5pGNmvaLnk4B3gMeixzvRtGaZWQ8z+42ZvWpmr5vZnZkKLV902sgS6l7ayMED+9n/\n6V52VFUC8Eb1Ziqfeohr7niwvrclTcuG7aiMcrya6+E/Dkwi9cOsE100rcFzSxdPOwBc4O57zawb\nsMXMnnP3V9oeW441YPAIRo27hPuuu4KevfswYMhIANYsnMuhg59RdtsPARg0rIgrb9C/vU3Jhu2o\njHK8mjvxalL0fNrxNOzuDuyN3naLHn48bUl6Jlx9LROuvhaA8sceAGD2I+VJRspK2bAdlVGORzon\nXhmpsfrTovH8AuAUd/9NGp/tSuovhDOAhe5e1cgy04HpAAUFBa2MH7YFFW83Oe/j9/4f1m0fdc0s\nA3D9+DMyHSsrNbUtO9J2VEZpq3SO0vkn4M+krp0zl9Qdr1YCZ7X0QXc/DIwyszxgtZmNdPe6Y5Yp\nA8oASkpK9BdAhuSdp9/TMyEbtqMySrrSOQ7/W+7+N8B+AHf/T6B7a1bi7h8DFaTO0BURkQSkU/AP\nRkMzDmBm+aR6/M0ys/yoZ4+Z5QITgTfakFVERNognSGdXwCrgX5mNg+4Cvj7ND73FWBp9I9FF+AJ\nd1933ElFRKRN0jnxapmZ1QATSB2S+V/cfUcan9sGfKPtEUVEJBPS6eEDvAX86cjyZlbg7v8WWyoR\nEcm4dA7L/DFwO/AhqZuYHznx6sx4o4mISCal08O/ERjq7v837jAiIhKfdI7S2UXqDlciIpLFmuzh\nN7i14TtApZk9S4Pr37v7fTFnExGRDGpuSOfE6Pnfokd3WnnClYiIdBzNXTxNl7ATEelE0hnDFxGR\nTkAFX0QkEC0W/MbubmVmx3WNfBERSU46Pfy1R253CGBmw4G18UUSEZE4pFPw7yZV9Hua2WjgSeCv\n4o0lIiKZls7F056N7klbTupQzcnuvjP2ZCIiklHNnXj1AEffg7Y38H+A680Md78h7nAiIpI5zfXw\nq495XxNnEBERiVdzJ14tBTCzLwH7o/vTHrkx+V+0TzwREcmUdH603QTkNnifC2yMJ46IiMQlnYLf\nw933HnkTvT4hvkgiIhKHdAr+J2ZWfORNdGjmvvgiiYhIHNK5AcpM4Ekz+4DU3a5OAabEmkpERDIu\nnePwt5rZMGBoNOlNdz8YbywREcm0dG9iPhQYDvQAiqPj8B+NL5aIiGRaOjcxvx04n1TB/xVwMbAF\nUMEXEcki6fxoexUwAfgPd78GKCJ11q2IiGSRdIZ09rn7n83sUHTVzN8DA2POFaR1i+ezvaqCrjnd\n6HNqAVNuvpvcnr1a/qBkJe3vzCj7hzt5pfJ5crp149SBhdzys/vp2Ut90sak08OvNrM8YDGpyyv8\nFng51lSBGlx8DrMWrWVW6TPk9y/khV+WJR1JYqT9nRnFZ49j8ZpKylZX0H/Q6Sxf/IukI3VY6Ryl\nc130stTM1gO93H1bvLE6v2WL7uf5p58g76S+5J9yKkNGnMnQC79fP79gWBGvbdmQYELJpE3LS6ne\nuJqevfuQl38K/QeP4PyrptXP1/5OT2PbceZNs+rnf61oNJvL1yWYsGNL545Xm468dvf33H1bw2nS\nejtff5XK59ZQunIj80qXsbOu9gvLbC1fydCSsQmkk0zb/VYdtS8+y00L1zBtbhm7dtZ9YRnt75al\nsx03rFrOWd++IIF02aG5yyP3IHUJhb5m9mVSJ10B9AL6t0O2TquupopzJ1xMj9zUFSrOHv/do+Zv\nWl5Kl645FF9wWRLxJMPerath5DkT6d4jdUmq4WPGHzVf+zs9LW3HZYvup2tODhMmXZlEvKzQ3JDO\nDFJn2Z5Kauz+SMH/E7Ag5lzB2lq+iu1VFcy4Zwlm1vIHJKtpf2fGhtUrqHrxeeY/9KS2YzOaHNJx\n939099OAW9z9dHc/LXoUuXuLBd/MBppZhZltN7PXzezGjCbPYl8vGcNLL6znwP59fPrJXl6uLAfg\njerNVD71ENfc8WB9L0ay32kjS6h7aSMHD+xn/6d72VFVCWh/t1ZT23Hr5hd44uGF3LVgaf1fzdK4\ndA7L/A8zO9Hd95jZ3wPFwM/c/bctfO4QMMvdf2tmJwI1Zva8u29va+hsN3j4mYy76Apm/OUE8k7q\ny9CRowBYs3Auhw5+RtltPwRg0LAirrzhziSjSgYMGDyCUeMu4b7rrqBn7z4MGDIS0P5uraa244J5\nt3Hw4Gf83Y9Sl/j6WtFoZt4+P8moHVY6Bf+n7v6kmZ0HXAjcCzwIfKu5D7n7vwP/Hr3eY2Y7SI39\nB1/wAabOmMnUGTMBeHThvQDMfqQ8yUgSowlXX8uEq68FoPyxBwDt7+PR2HZcuv6VJCNllXSOwz8c\nPV8KlLn7s0D31qzEzAqBbwBVrfmciIhkTjo9/PfNbBEwEfgfZvYXpPcPBQBm1hNYCcx09z81Mn86\nMB2goKAg3Waz0o8ePfY2wZETU0cbbKh4u9nP//Nfl2Q6EqMG5nX4NrMxY5P7GmDAxQDUtfP+zsbt\nCM1sy2g7Nrutied7k63SKdz/DdgAfNfdPwZOAm5Np3Ez60aq2C9z91WNLePuZe5e4u4l+fn5acYW\nEZHWSudM20+BVQ3e14/NN8dSx0Y9BOxw9/vaElJERNou7aGZ43Au8APgAjOrjR6XxLg+ERFpRro3\nQGk1d9/C5ydriYhIwuLs4YuISAeigi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCYQKvohI\nIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8\nEZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKRk3SAbFb2D3fySuXz5HTrxqkDC7nl\nZ/fTs1fvpGOJSBvceuutrF27lu7du/PVr36VRx55hLy8vKRjZYR6+G1QfPY4Fq+ppGx1Bf0Hnc7y\nxb9IOpKItNHEiROpq6tj27ZtDBkyhJ///OdJR8oY9fDTNG/ePJYuXUq/fv0YOHAgo0ePpuSSH9TP\n/1rRaDaXr0swoYi01rJF9/P800+Qd1Jf8k85lSEjzmTRvXfWzx8zZgxPPfVUggkzSwU/DTU1NaxY\nsYLa2loOHTpEcXExo0ePPmqZDauWM+7iKxJKKCKttfP1V6l8bg2lKzdy+PBhrrtqIkNGnHnUMg8/\n/DBTpkxJKGHmqeCnYfPmzUyePJkTTjgBgMsvv/yo+csW3U/XnBwmTLoyiXgichzqaqo4d8LF9MhN\nfa/PHv/do+bPmzePnJwcpk6dmkS8WKjgt9GG1SuoevF55j/0JGaWdBwRyYAlS5awbt06Nm3a1Km+\n17H9aGtmD5vZ782sLq51tJexY8eyZs0a9u3bx549e1i7di0AWze/wBMPL+SuBUvrewkikh2+XjKG\nl15Yz4H9+/j0k728XFkOwPr165k/fz7PPPNM/V/1nUWcPfwlwALg0RjX0S6Ki4uZMmUKRUVF9OvX\nj7POOguABfNu4+DBz/i7H6XG+L5WNJqZt89PMqqIpGnw8DMZd9EVzPjLCeSd1JehI0cBcP3113Pg\nwAEmTpwIpH64LS0tTTJqxsRW8N3912ZWGFf77W3OnDnMmTMHgDvuuAOApetfSTCRiLTV1BkzmTpj\nJgCPLrwXgLfffjvJSLFKfAzfzKYD0wEKCgoSTvO5wtnPNjnv4y07sW659P6outk23rvn0oxmunD4\nyRltL1vaVMaO2V4cbbZHxqa+2x+/+gHWLZcNzXz3j8j0d7u9JF7w3b0MKAMoKSnxhOOkJe+8zvOr\nvYikhPC91pm2IiKBUMEXEQlEnIdlLgdeBoaa2W4zmxbXukREpGVxHqVzdVxti4hI62lIR0QkECr4\nIiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8EZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEgg\nVPBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCYQKvohIIFTwRUQCoYIvIhIIFXwR\nkUCo4IuIBCKYgv/kk08yYsQIunTpQnV1ddJxRCQgP/3pTznzzDMZNWoU3/nOd/jggw8SyRFMwR85\nciSrVq1i7NixSUcRkcDceuutbNu2jdraWiZNmsRdd92VSI6cRNYas3nz5rF06VL69evHwIEDGT16\nNLfcckvSsUQkAC3Vn08++QQzSyRbpyv4NTU1rFixgtraWg4dOkRxcTGjR49OOpaIBKC5+jNnzhwe\nffRRevfuTUVFRSL5Ot2QzubNm5k8eTInnHACvXr14vLLL086kogEorn6M2/ePHbt2sXUqVNZsGBB\nIvk6XcEXEenIpk6dysqVKxNZd6wF38wuMrM3zextM5sd57qOGDt2LGvWrGHfvn3s2bOHtWvXtsdq\nRUSarD9vvfVW/TJPP/00w4YNSyRfbGP4ZtYVWAhMBHYDW83sGXffHtc6AYqLi5kyZQpFRUX069eP\ns846C4DVq1fz4x//mD/84Q9ceumljBo1ig0bNsQZRUQC01T9mT17Nm+++SZdunRh0KBBlJaWJpIv\nzh7+N4G33f0dd/8MWAFcEeP66s2ZM4edO3eyZcsWhgwZAsDkyZPZvXs3Bw4c4MMPP1SxF5FYNFZ/\nVq5cSV1dHdu2bWPt2rX0798/kWxxFvz+wK4G73dH00REJAHm7vE0bHYVcJG7/yh6/wPgW+5+/THL\nTQemR2+HAm/GEih9fYGPOnib2ZAxjjaVsWO2ly1tZkPG4zHI3fPTWTDO4/DfBwY2eD8gmnYUdy8D\nymLM0SpmVu3uJR25zWzIGEebytgx28uWNrMhY9ziHNLZCgw2s9PMrDvwPeCZGNcnIiLNiK2H7+6H\nzOx6YAPQFXjY3V+Pa30iItK8WC+t4O6/An4V5zpiEMfwUqbbzIaMcbSpjB2zvWxpMxsyxiq2H21F\nRKRj0aUVREQCoYIvHZ6ZFZpZXUdtL642s4H2TXZRwRcRCYQKfozMbI2Z1ZjZ69EJZkG0GUdGIMfM\nlpnZDjN7ysxO6GDtZbzNbNjXkeD2TdZydz1iegAnRc+5QB3QJ4Q2Y2ivEHDg3Oj9w8AtHaW9GNvM\nhn0d5L7J1od6+PG6wcxeBV4hddbx4EDajCPjLnf/39HrfwHO62DtxdFmNuxrCHPfZKVOd4vDjsLM\nzgcuBM5290/NrBLo0dnbjCNj5Njjh9t6PHGm28tom9mwrxsIat9kM/Xw49Mb+M/oizUMGBNIm3Fk\nBCgws7Oj198HtnSw9jLdZjbs6yNC2zdZSwU/PutJ/VC0A7iH1J/QIbQZR0ZIXUX1b6J2vww82MHa\ny3Sb2bCvjwht32QtnWkrIhII9fBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKviSlczspRjaLDSz\n77fyM7e1MP9XZpbXtmQimaHDMkUi0Zmot7j7pFZ8Zq+792xkupH6fv05gxFF2kQ9fMlKZrY3ej7f\nzCqjKyC+EV0R0aJ575nZfDN7zcx+Y2ZnRNOXmNlVx7ZF6mSkb5tZrZnddMz6vmJmv47m1ZnZt83s\nHiA3mrYs+gvhTTN7lNSFyQZGGfpG83aY2eLoSpXlZpYbtX2WmW2L2rnXdO12iYkKvnQG3wBmAsOB\n04FzG8z7o7t/HVgA3N9CO7OBze4+yt3/1zHzvg9scPdRQBFQ6+6zgX3R8lOj5QYD/+TuI9z9d8e0\nMRhY6O4jgI+BK6PpjwAzorYPp/nfLNJqKvjSGfzG3XdHwye1pC6He8TyBs9nH/vBVtgKXGNmdwBf\nd/c9TSz3O3dv6pIF77p7bfS6BiiMxvdPdPeXo+mPtyGjSLNU8KUzONDg9WGOvgqsN/L6ENH/+2bW\nBeje0grc/dfAWOB9YImZ/XUTi35ynDlFYqeCL53dlAbPR3rR7wGjo9eXA92i13uAExtrxMwGAR+6\n+2Lgn4HiaNZBM+vW2GfS4e4fA3vM7FvRpO8db1siLVHBl87uy2a2DbgROPJD7GJgXHQjkLP5vFe+\nDThsZq8e+6MtcD7wqpn9K6l/PP4xml4GbDOzZW3IOA1YbGa1wJeAP7ahLZEm6bBM6bTM7D2gxN0/\nSjpLc8ysp7sfOepoNvAVd78x4VjSCWkMUSR5l5rZT0h9H38H/Pdk40hnpR6+iEggNIYvIhIIFXwR\nkUCo4IuIBEIFX0QkECr4IiKBUMEXEQnE/wdcnX6ad27xGAAAAABJRU5ErkJggg==\n", "text/plain": [ "" ] }, "metadata": {}, "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 resulting sub-run wouldn't begin and end with the same stack:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAH9lJREFUeJzt3Xl4VOX99/H3FxKWIIsIQYSEsIrIZggFimIRoVoQpVZR\n+enT1l7YKi6tYkGePrX+jCC2FREUUFCwIEVRNhXcQGLdSCBENEolQBURtAoi+3I/f8yAAbJMzJyc\nmTmf13XNlZlzztznwzk5X+6c1ZxziIhI4qvmdwAREakaKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4\nIiIBoYIvIhIQKvgiIgGhgi8iEhBJfgcorlGjRi4jI8PvGL75dt/BqLe5Y0/02xT5oRqkJEe9zXq1\not9mPMnLy/vKOdc4kmljquBnZGSQm5vrdwzfvPrhtqi3uTB/S9TbFPmhLu3aLOptXtihSdTbjCdm\ntjnSabVLR0QkIFTwRUQCQgVfRCQgVPBFRAJCBV9EJCBU8EVEAkIFX0QkIFTwRUQCIqYuvJJg+tec\nCWxcvZLqScnUb9KcfsPvpmadun7HEkk46uGL79I69uCa++dx9bh/0uD0FuQtesLvSCIJST18qVK5\nC6ZTmLOElHqncsppp9O4ZXsyB153bHyTNh3Z8N5rPiYUSVzq4UuV2b6xkPVvL+Oq++ZwyciJbC/6\n4KRpCt9YRIsuvX1IJ5L41MOXKvP5R2to3b0vyTVrA5CRef5x43MXTKda9eq0632xH/FEEp56+BIT\nCt9YxMY1OfS/8V7MzO84IgnJ04JvZpvM7H0zyzez4N73WAA4o/05FOWu4NCBfRzYu5tNq1cCsHnt\nW6xeMotBtz94rPcvItFXFbt0+jrnvqqC+UiMS215Fm17DuDp0VeTUu9UUlt1AGDlzPs5fPAgC8fe\nCECTNp3oe/1dfkYVSUjahy9VKuuy68m67HoA3p0/FYBr/77Qz0gigeH1PnwHvGxmeWY23ON5iYhI\nGbzu4Z/rnNtiZqnAK2b2kXNuZfEJwv8RDAdIT0/3OI74YXHB1pJHtB0MwJbSxodd0rlptCOJBJKn\nPXzn3Jbwz+3A88CPSphmmnMuyzmX1bhxRM/hFRGRH8Czgm9mdcys7tH3wABgnVfzExGRsnm5S6cJ\n8Hz4nOokYI5zbqmH8xMRkTJ4VvCdc0VAF6/aFxGRitGVtiIiAaGCLyISECr4IiIBoYIvIhIQKvgi\nIgGhgi8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4IiIB\noYIvIhIQKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIiAZHk\ndwCJL/+aM4GNq1dSPSmZ+k2a02/43dSsU9fvWCeJl5yxTssxsaiHLxWS1rEH19w/j6vH/ZMGp7cg\nb9ETfkcqUbzkjHVajolFPXwpVe6C6RTmLCGl3qmcctrpNG7ZnsyB1x0b36RNRza895qPCUPiJWes\n03JMfOrhS4m2byxk/dvLuOq+OVwyciLbiz44aZrCNxbRoktvH9J9L15yxjotx2BQD19K9PlHa2jd\nvS/JNWsDkJF5/nHjcxdMp1r16rTrfbEf8Y6Jl5yxTssxGNTDlworfGMRG9fk0P/GezEzv+OUKl5y\nxjotx8ThecE3s+pmtsbMlng9L4meM9qfQ1HuCg4d2MeBvbvZtHolAJvXvsXqJbMYdPuDx3qDfoqX\nnLFOyzEYqmKXzq1AIVCvCuYlUZLa8iza9hzA06OvJqXeqaS26gDAypn3c/jgQRaOvRGAJm060ff6\nu5Qzzmk5BoM557xr3Kw5MBPIBv7gnBtU1vRZWVkuNzfXszyx7tUPt0W9zYX5W6LSzrvzp5Jcq/Zx\nZ21EanHB1krN+5LOTSOetjI55XteLcdLuzaLansAF3ZoEvU244mZ5TnnsiKZ1utdOhOAO4EjHs9H\nRETK4dkuHTMbBGx3zuWZ2U/KmG44MBwgPT3dqzgSoVJ7420HA7Algt56RXrkP0SZfzFEmNPrjPFA\nyzF4vOzh9wYGm9kmYC5wgZn948SJnHPTnHNZzrmsxo0bexhHRCTYPCv4zrnRzrnmzrkM4Crgdefc\n/3g1PxERKZvOwxcRCYgqudLWObcCWFEV8xIRkZKphy8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQ\nKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIiAVFuwTezKyIZ\nJiIisS2SHv7oCIeJiEgMK/UBKGZ2MfAzoJmZTSw2qh5wyOtgIiISXWU98epzIBcYDOQVG74L+L2X\noUREJPpKLfjOubXAWjOb45w7WIWZRETEA5E80/ZHZnY30CI8vQHOOdfKy2AiIhJdkRT86YR24eQB\nh72NIyIiXomk4O90zr3keRIREfFUWWfpZIbfLjezB4DngP1HxzvnVnucTUREoqisHv7fTvicVey9\nAy6IfhwREfFKWWfp9K3KICIi4q1y9+Gb2R9KGLwTyHPO5Uc/kkTTv+ZMYOPqlVRPSqZ+k+b0G343\nNevU9TtW3ImH5RgPGaf99S+8s+IVkpKTOSMtgzvuncAp9er7HSswIrm1QhbwW6BZ+HUDcBHwmJnd\n6WE2iYK0jj245v55XD3unzQ4vQV5i57wO1JcioflGA8ZM3udz2MLVjDt+eU0a9GKpx+bWP6XJGoi\nOUunOZDpnPsOwMz+DLwA9CF0quZ47+JJRcyeOoFXFs6jQcNGND79DNqd3Zn0cy49Nr5Jm45seO81\nHxPGh9wF0ynMWUJKvVM55bTTadyyPZkDrzs2PhaWY7xmvHTM97fhOqtLN3JeXuJjwuCJpIefSrGz\nc4CDQBPn3N4ThouP1n+wlhUvLWDK/FfJnjKb9etO3ttW+MYiWnTp7UO6+LF9YyHr317GVffN4ZKR\nE9le9MFJ0/i9HBMl47Lnnqb7eTr3oypF0sOfDbxrZgvDny8B5phZHeBDz5JJhazLe5fe/S6mVu0U\nAHr1/elx43MXTKda9eq0632xH/HixucfraF1974k16wNQEbm+ceNj4XlmAgZZ0+dQPWkJPoNutyP\neIFVbsF3zv2vmb0EHO0u/NY5lxt+P8yzZBI1hW8sYuOaHC6761HMzO84cSselmM8ZFz2/FzefeMV\nxk9/JmYzJqpSd+mYWb3wz4ZAEfBU+FUUHlYmM6tlZu+Z2Voz+8DM/hKt0HKyTlk9eev1pezft5c9\nu7/j7RUvA7B57VusXjKLQbc/eKy3JaU7o/05FOWu4NCBfRzYu5tNq1cCsbUc4znjqpzXmTdjMvdM\nmnnsr1GpOmX18OcAgwgdmHWEb5pW7Gd5N0/bD1zgnPvOzJKBN83sJefcO5WPLSdq26Ez5190KTf8\nvB8NGjbizI5dAVg5834OHzzIwrE3AtCkTSf6Xn+Xn1FjWmrLs2jbcwBPj76alHqnktqqAxBbyzGe\nM07KvouDBw/wx98MBUIHbm/7s877qCrmnPN+JmYpwJvA75xz75Y2XVZWlsvNzS1tdMJ79cNtUWtr\n1uQHqJ1ShxrFztKJxOKCrZWe9yWdm0a1zWi3V1KbpXl3/lSSa9U+7gyY0rT+aA1dVr3Oc9feXtl4\nxwyc9whFZ3alsMuPo5KxOD+W41/GRP9heRd2aBL1NuOJmeU557LKnzKyC6+M0L76luH9+enA6c65\n9yL4bnVCfyG0ASaXVOzNbDgwHCA9PT2SzBL2m1ml/+e4Y+3nWHJt6lcve6N+/Lrjf0+iUQQu7dos\nqm1Gu72S2ixtWe7YtgtLPsSWcub5+HVZpL3/ImcunUO9K4bwTc/zKp2xbuH79Fg4naIbfk+7rldE\nJWNxfizHsn5n4eSMEl2RnKXzCHCE0L1z/pfQE6/mA93L+6Jz7jDQ1cwaAM+bWUfn3LoTppkGTINQ\nD79i8aU0Dc7V8fRoqMhy3HLltbR48lHaPDSWVT3OhUoekGz18P0crFef//zyt1HL6Jd4yBgEkZyH\n38M5dxOwD8A59w1QoyIzcc7tAJYTukJXJCEdqVmLot/+gfoFq2m0/OVKtVV/zSoav/Eqm399E4d0\n6wGJkkgK/sHwrhkHYGaNCfX4y2RmjcM9e8ysNtAf+KgSWUVi3tbLhrInLYPWD98PR8rdTErmHK0f\nGsv+0xrxn2HXRzegBFokBX8i8DyQambZhA6+3hfB95oSupd+AbAKeMU5p+uoJaG55GQ2jLiTuus/\npMnSRT+ojYbv5NBw1VtsGn4bR1LqRDmhBFkkF17NNrM8oB+hUzIvc84VRvC9AuCcykcUiS/bfnYZ\nLR+fSKvJD7B9wCBcUiSHysLCvft9pzfjsyuv9S6kBFIkPXyAfxPq5S8CdofP1BGRklSrxoab/0id\nTRtoumhehb7aaPnL1H9/DUW/+wOuRk2PAkpQlVvwzexmYBvwCrCE0J0ytWtGpAxfXnAROzt2peUj\nf8MORHiPwSNHaP3wOPakt2TrpVd6G1ACKZIe/q3Amc65s51znZ1znZxznb0OJhLXzNhwyyhqb91C\n82eeiugrTV5aSN31hWy4aSQuOdnjgBJEkRT8Twk94UpEKuDrH5/PN1k9yZj6ENX27C5zWjt0iFaT\nH+C7tu3Z9rPLqiihBE1ZN0/7Q/jxhkXACjMbfXRYKY89FJHizPjkltHU/O+XpM2ZUeakTRfOo87m\nIjbcMgqqRXpoTaRiyvrNqht+/YfQ/vsaxYbF1oMyRWLUzm49+Oq8C8iYPpnqu74tcRo7sJ+Wj/6N\nnZ3O4csTnmMgEk2lni/mnNPtjEWiYMMto+hxxQBazJxC0YiTHwPd/JmnqL11C4X3/L3St2MQKYv+\ndhTx2K4OndnWfyDpM6eS/M1/jxtXbc9uMqY+xDfde/F1rz4+JZSgUMEXqQJFI+6k+t49tJg+6bjh\naXNmUPO/X/LJLaPVuxfPRXIe/klPtzKzlt7EEUlMu9ucyReXXE7anCeosf0LAJK+3UnG9Ml8dd4F\n7Mz8kc8JJQgi6eEvPvq4QwAz6wAs9i6SSGIqunEkdvgQLac8CED6zCkkf7sjdGaOSBWIpODfR6jo\nn2Jm3YBngP/xNpZI4tmb1oLPL7+GZvNnU3ddPumzprFtwCB2ddB1jFI1Irl52gvhZ9K+TOh0zCHO\nufWeJxNJQBtv+D1NF8zj7Ltuofq+vWwo4awdEa+UWvDN7GHC98APqw9sAEaYGc65W7wOJ5Jo9jdp\nytbBV9Dsmaf4su9P2dO6nd+RJEDK6uGf+PDJPC+DiASFHTgAQLVDh3xOIkFT1oVXMwHMrA6wL/x8\n2qMPJtd9W0V+gNqfbqbpC/PZ1aETjXJeo27h++w6q5PfsSQgIjlo+xpQu9jn2sCr3sQRSWwtH/kr\nrnoS68ZN5mC9BrSeOM7vSBIgkRT8Ws65745+CL9P8S6SSGJK2bCepkvm89nVv2RP63Zs+vVNNFr5\nGvXXrPI7mgREJAV/t5llHv0QPjVzr3eRRBJT60njOVyrNpt+czMAnw77NftPa0zrh8aCc+V8W6Ty\nIin4twHPmFmOmb0J/BMY4W0skcRSt/B9mry8hP9cN5yDp54GwJGUOmwafisNV71Fw3dyfE4oQVBu\nwXfOrQLaA78Dfguc5ZzTGTsiFdB64jgO1mvA5l/+7rjhn115LftOb6ZevlSJSG+edibQAcgErjaz\n67yLJJJY6q9+j0YrX2PT9TdxuG6948a5GjUpuvF26r+/hsbLl/mUUIIikpun/Rl4OPzqC4wHBnuc\nSyQxOEebiWPZf1pjPr3m1yVOsvXSK9ndohWtHr4fjhyp4oASJJH08H8B9AO+cM79CuhC6KpbESlH\nw7dXcuqqt9l0w60cSalT4jQuKYmim0ZSd30hTV5aWMUJJUjKvZcOsNc5d8TMDoXvmrkdSPM4VyBN\n++tfeGfFKyQlJ3NGWgZ33DuBU+rp/9a45RytHxrL3qbN+OyKa08afdz6bt6Cp1u3o9XkB9j+00tw\nSZFsmgIwcuRIFi9eTI0aNWjdujVPPPEEDRo08DtWTIqkh59rZg2AxwjdXmE18LanqQIqs9f5PLZg\nBdOeX06zFq14+rGJfkeSSmi8fBn11+Wz8Xe342qcfHH6ces7ozX/r2Ub6mwuounCeT6kjV/9+/dn\n3bp1FBQU0K5dO8aOHet3pJgVyd0ybwy/nWJmS4F6zrkCb2MlvuzsbGbOnElqaippaWl069aNrJ99\n3ws8q0s3cl5e4mNCqZQjR2g9cRy7W7Ri66VXMnvqBF5ZOI8GDRvR+PQzaHd2Z6741Y3HJj+rSzdy\ntn3Ozk7n0OqRv7H1kstL/E8i6EpajlMf+P7x2z179uTZZ5/1MWFsi+Sg7WtH3zvnNjnnCooPk4rL\ny8tj7ty55Ofn8+KLL7Jq1clXWi577mm6n3eBD+kkGpq8uIBT/v0RRSPu5OOPP2DFSwuYMv9VsqfM\nZv26/JOmD63vfmy4dTS1vthC83lP+ZA6tq3/YG25y3HGjBlcfPHFPqSLD2XdHrkWoVsoNDKzU4Gj\nD9ysBzSrgmwJKycnhyFDhpCSErpDxeDBx5/0NHvqBKonJdFv0OV+xJNKsoMHaT35AXa168C2iwaz\n7h+P07vfxdSqHVrfvfr+9Ljpi6/vr4Gvu/+YjGkT2PLzq0s90BtE6/LeLXM5Zmdnk5SUxLBhw/yI\nFxfK6uHfQGifffvwz6OvhcCkMr4nlbDs+bm8+8YrjLp/MqaHWselpgvnkfKfjWy4+Y9Qrew/ok9a\n32ZsuHU0Nf/7FWmzZ1RR4vj35JNPsmTJEmbPnq3tpgyl/jY65x5yzrUE7nDOtXLOtQy/ujjnyi34\nZpZmZsvN7EMz+8DMbo1q8jjWp08fFixYwN69e9m1axeLF4ceEbwq53XmzZjMPZNmHuvFSHyxA/tp\n9ejf2dnpHL7qOwCATlk9eev1pezft5c9u7/j7RUvA6Wv753ndOerPv3ImDGZpG93+vLviEWlLcel\nS5cyfvx4Fi1adOyvZilZJOd+fWFmdZ1zu8zs/xK62vZe59zqcr53CLjdObfazOoCeWb2inPuw8qG\njneZmZkMHTqULl26kJqaSvfu3QGYlH0XBw8e4I+/GQqEDuTd9ufxfkaVCmo+7ylqfbGFD+99EMI9\nzbYdOnP+RZdyw8/70aBhI87s2BUoe31vuGUUPX7Rn/SZUyi6+Y/+/GNiTGnLccSIEezfv5/+/fsD\noQO3U6ZM8TNqzIqk4P/JOfeMmZ0LXAg8ADwK9CjrS865rcDW8PtdZlZIaN9/4As+wJgxYxgzZgwA\nd999NwAzl77jYyKprGp7dpMxbQJfd/8xX/c877hxw264jWE33AbArMkPAGWv711ndWLbgEGkz5rG\np8Ou52DDRt4FjyMlLcdPPvnEz0hxJZLz8A+Hfw4EpjnnXgBqVGQmZpYBnAO8W5HvicST9NnTqfnf\nr9hw6+hjvfvK2DDiTqrv20vG4w9HIZ1IZD38LWY2FegP3G9mNYn8pmuY2SnAfOA259y3JYwfDgwH\nSE9Pj7TZuJQx6oVSxnSHfcCsEx8jfLxN4wZGPdOFHZrEfJtxk/H/XAGn1ab7sEFlrGugbl8AlkWy\nvsePp0WvXrSIQt64WY4nKHVZhpdjmcsab7abeBVJwb8SuAj4q3Nuh5k1BUZG0riZJRMq9rOdc8+V\nNI1zbhowDSArK0v3h5X41bVr6BVNt98e3fYk0CK50nYP8Fyxz8f2zZfFQudGTQcKnXN/r0xIERGp\nvIh3zfwAvYFrgQvMLD/8+pmH8xMRkTJ4dks+59ybfH91roiI+MzLHr6IiMQQFXwRkYBQwRcRCQgV\nfBGRgFDBFxEJCBV8EZGAUMEXEQkIFXwRkYBQwRcRCQgVfBGRgFDBFxEJCBV8EZGAUMEXEQkIFXwR\nkYBQwRcRCQgVfBGRgFDBFxEJCBV8EZGAUMEXEQkIFXwRkYBQwRcRCQgVfBGRgFDBFxEJCBV8EZGA\nUMEXEQkIFfxKGDlyJO3bt6dz584MGTKEHTt2+B1JRCopkbdrFfxK6N+/P+vWraOgoIB27doxduxY\nvyOJSCUl8nad5HeAeJGdnc3MmTNJTU0lLS2Nbt26cccddxwb37NnT5599lkfE4pIRQVtu1bBj0Be\nXh5z584lPz+fQ4cOkZmZSbdu3Y6bZsaMGQwdOtSnhCJSUUHcrlXwI5CTk8OQIUNISUkBYPDgwceN\nz87OJikpiWHDhvkRT0R+gCBu1yr4lfTkk0+yZMkSXnvtNczM7zgiEgWJul17dtDWzGaY2XYzW+fV\nPKpKnz59WLBgAXv37mXXrl0sXrwYgKVLlzJ+/HgWLVp0rJcgIvEhiNu1lz38J4FJwCwP51ElMjMz\nGTp0KF26dCE1NZXu3bsDMGLECPbv30///v2B0AGeKVOm+BlVRCIUxO3as4LvnFtpZhletV/VxowZ\nw5gxYwC4++67Afjkk098TCQilRW07dr3ffhmNhwYDpCenu5zmu9ljHqh1HE73lyPJddm0lelTwOw\nadzAaMcSkUoqbduOdLuG+N22fS/4zrlpwDSArKws53OciDQ4N3GO2otISBC2a11pKyISECr4IiIB\n4eVpmU8DbwNnmtlnZna9V/MSEZHyeXmWztVetS0iIhWnXToiIgGhgi8iEhAq+CIiAaGCLyISECr4\nIiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIi\nAaGCLyISECr4IiIBoYIvIhIQKvgiIgGhgi8iEhAq+CIiAaGCLyISECr4IiIBoYIvIhIQgSn4zzzz\nDGeffTbVqlUjNzfX7zgiEiB/+tOf6Ny5M127dmXAgAF8/vnnvuQITMHv2LEjzz33HH369PE7iogE\nzMiRIykoKCA/P59BgwZxzz33+JIjyZe5eiw7O5uZM2eSmppKWloa3bp144477vA7logEQHn1Z/fu\n3ZiZL9kSruDn5eUxd+5c8vPzOXToEJmZmXTr1s3vWCISAGXVnzFjxjBr1izq16/P8uXLfcmXcLt0\ncnJyGDJkCCkpKdSrV4/Bgwf7HUlEAqKs+pOdnc2nn37KsGHDmDRpki/5Eq7gi4jEsmHDhjF//nxf\n5u1pwTezi8zsYzP7xMxGeTmvo/r06cOCBQvYu3cvu3btYvHixVUxWxGRUuvPv//972PTLFy4kPbt\n2/uSz7N9+GZWHZgM9Ac+A1aZ2SLn3IdezRMgMzOToUOH0qVLF1JTU+nevTsAzz//PDfffDNffvkl\nAwcOpGvXrixbtszLKCISMKXVn1GjRvHxxx9TrVo1WrRowZQpU3zJ52UP/0fAJ865IufcAWAucKmH\n8ztmzJgxrF+/njfffJN27doBMGTIED777DP279/Ptm3bVOxFxBMl1Z/58+ezbt06CgoKWLx4Mc2a\nNfMlm5cFvxnwabHPn4WHiYiID8w5503DZr8ALnLO/Sb8+Vqgh3NuxAnTDQeGhz+eCXzsSaDINQK+\nivE24yGjF20qY2y2Fy9txkPGH6KFc65xJBN6eR7+FiCt2Ofm4WHHcc5NA6Z5mKNCzCzXOZcVy23G\nQ0Yv2lTG2GwvXtqMh4xe83KXziqgrZm1NLMawFXAIg/nJyIiZfCsh++cO2RmI4BlQHVghnPuA6/m\nJyIiZfP01grOuReBF72chwe82L0U7TbjIaMXbSpjbLYXL23GQ0ZPeXbQVkREYoturSAiEhAq+BLz\nzCzDzNbFantetRkPtG7iiwq+iEhAqOB7yMwWmFmemX0QvsAsEG16kRFIMrPZZlZoZs+aWUqMtRf1\nNuNhXYcFbt3ELeecXh69gIbhn7WBdcBpQWjTg/YyAAf0Dn+eAdwRK+152GY8rOtArpt4famH761b\nzGwt8A6hq47bBqRNLzJ+6pz7V/j9P4BzY6w9L9qMh3UNwVw3cSnhHnEYK8zsJ8CFQC/n3B4zWwHU\nSvQ2vcgYduL5w5U9nzja7UW1zXhY18UEat3EM/XwvVMf+Ca8YbUHegakTS8yAqSbWa/w+2uAN2Os\nvWi3GQ/r+qigrZu4pYLvnaWEDhQVAuMI/QkdhDa9yAihu6jeFG73VODRGGsv2m3Gw7o+KmjrJm7p\nSlsRkYBQD19EJCBU8EVEAkIFX0QkIFTwRUQCQgVfRCQgVPAlLpnZWx60mWFm11TwO3eVM/5FM2tQ\nuWQi0aHTMkXCwlei3uGcG1SB73znnDulhOFGaPs6EsWIIpWiHr7EJTP7LvzzJ2a2InwHxI/Cd0S0\n8LhNZjbezN43s/fMrE14+JNm9osT2yJ0MdJ5ZpZvZr8/YX5NzWxleNw6MzvPzMYBtcPDZof/QvjY\nzGYRujFZWjhDo/C4QjN7LHynypfNrHa47e5mVhBu5wHTvdvFIyr4kgjOAW4DOgCtgN7Fxu10znUC\nJgETymlnFJDjnOvqnHvwhHHXAMucc12BLkC+c24UsDc8/bDwdG2BR5xzZzvnNp/QRltgsnPubGAH\ncHl4+BPADeG2D0f4bxapMBV8SQTvOec+C+8+ySd0O9yjni72s9eJX6yAVcCvzOxuoJNzblcp0212\nzpV2y4KNzrn88Ps8ICO8f7+uc+7t8PA5lcgoUiYVfEkE+4u9P8zxd4F1Jbw/RPh338yqATXKm4Fz\nbiXQB9gCPGlm15Uy6e4fmFPEcyr4kuiGFvt5tBe9CegWfj8YSA6/3wXULakRM2sBbHPOPQY8DmSG\nRx00s+SSvhMJ59wOYJeZ9QgPuuqHtiVSHhV8SXSnmlkBcCtw9EDsY8D54QeB9OL7XnkBcNjM1p54\n0Bb4CbDWzNYQ+s/jofDwaUCBmc2uRMbrgcfMLB+oA+ysRFsipdJpmZKwzGwTkOWc+8rvLGUxs1Oc\nc0fPOhoFNHXO3epzLElA2oco4r+BZjaa0Pa4Gfilv3EkUamHLyISENqHLyISECr4IiIBoYIvIhIQ\nKvgiIgGhgi8iEhAq+CIiAfH/AQ1HQPNXLmVrAAAAAElFTkSuQmCC\n", "text/plain": [ "" ] }, "metadata": {}, "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": 13, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGdBJREFUeJzt3X10VfWd7/H3lwcRlAetBBSBoICoSDAJFRcOSi1OLUjh\n3s5FZey6Xcyisxw7zowyozK9ZdpGfLhXHa9OES8o3BHxAQkJWmjLiMTWqgnEDBqlysMoOlLvqi1a\nRLDf+8fZiQHzcJKcnX12fp/XWmflnLP3+e0Pe7O/+eV39oO5OyIi0v31SDqAiIh0DRV8EZFAqOCL\niARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEoheSQdo6pRTTvHCwsKkYyTm958cTjqC\nSOoMOL530hESVVNT84G7D85m3rwq+IWFhVRXVycdIzE/f+39pCOIpM5XzxmSdIREmdnebOfVkI6I\nSCBU8EVEAqGCLyISCBV8EZFAqOCLiARCBV9EJBB5dVimHG197b6kI0iOfWPisKQjSMDUwxcRCYR6\n+JK4X6y+h93bttKzV28GDjmdSxcsps8J/ZOOJdLtqIcviRs+/gKuvv1xrrrtMQYNHUlNxUNJRxLp\nltTDly5VXb6c+qoN9BtwEid+aSiDR42jeMa3GqcPGT2et17anGBCke5LPXzpMvt317PzhU1ceetq\nrlh4L/t3vfqFeeqfq2Bk0ZQE0ol0f+rhS5d59/XtnDlpGr379AWgsPjio6ZXly+nR8+ejJ1yeRLx\nRLo99fAlL9Q/V8Hu7VVMv/ZHmFnScUS6pVgLvpntMbN/N7NaMwv3uscCwGnjzmdX9RaOfPoJnx78\nmD3btgKw95Vfsm3DKmbecHdj719Ecq8rhnSmufsHXbAcyXMFo85mzOTLePTmq+g34CQKzjgHgK0r\nb+ezw4dZv+RaAIaMPo9p829JMqpIt6QxfOlSpbPnUzp7PgAvrn0AgGvuWp9kJJFgxD2G78BPzazG\nzBbEvCwREWlF3D38i9x9n5kVAD8zs9fdfWvTGaJfBAsARowYEXMcSUJl3XvNTxgzC4B9LU2PXDHh\n1FxHEglSrD18d98X/dwPrAO+3Mw8y9y91N1LBw/O6j68IiLSAbEVfDM7wcz6NzwHLgN2xLU8ERFp\nXZxDOkOAddEx1b2A1e6+McbliYhIK2Ir+O6+CyiKq30REWkfnWkrIhIIFXwRkUCo4IuIBEIFX0Qk\nECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyISCBV8EZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+\niEgg4r6nrYi0YX3tvqQjpMo3Jg5LOkJqqYcvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmE\nCr6ISCBU8EVEAqGCLyISCJ1pK+3yi9X3sHvbVnr26s3AIadz6YLF9Dmhf9KxviAtOfOd1mP3oh6+\ntMvw8Rdw9e2Pc9VtjzFo6EhqKh5KOlKz0pIz32k9di/q4UuLqsuXU1+1gX4DTuLELw1l8KhxFM/4\nVuP0IaPH89ZLmxNMmJGWnPlO67H7Uw9fmrV/dz07X9jElbeu5oqF97J/16tfmKf+uQpGFk1JIN3n\n0pIz32k9hkE9fGnWu69v58xJ0+jdpy8AhcUXHzW9unw5PXr2ZOyUy5OI1ygtOfOd1mMY1MOXdqt/\nroLd26uYfu2PMLOk47QoLTnzndZj9xF7wTeznma23cw2xL0syZ3Txp3PruotHPn0Ez49+DF7tm0F\nYO8rv2TbhlXMvOHuxt5gktKSM99pPYahK4Z0rgfqgQFdsCzJkYJRZzNm8mU8evNV9BtwEgVnnAPA\n1pW389nhw6xfci0AQ0afx7T5tyhnymk9hiHWgm9mpwMzgDLg7+JcluRe6ez5lM6eD8CLax8A4Jq7\n1icZqVlpyZnvtB67v7iHdO4B/h74Y8zLERGRNsTWwzezmcB+d68xs0tamW8BsABgxIgRccWRLFXW\nvdf8hDGzANjX0vQmrphwai4jfUGLGSHrnHFnTAOtx/DE2cOfAswysz3AGuArZvavx87k7svcvdTd\nSwcPHhxjHBGRsMVW8N39Znc/3d0LgSuBf3P3P49reSIi0jodhy8iEoguOdPW3bcAW7piWSIi0jz1\n8EVEAqGCLyISCBV8EZFAqOCLiARCBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGR\nQKjgi4gEQgVfRCQQKvgiIoFos+Cb2Z9l856IiOS3bHr4N2f5noiI5LEWb4BiZpcDXweGmdm9TSYN\nAI7EHUxERHKrtTtevQtUA7OAmibvHwD+Ns5QIiKSey0WfHd/BXjFzFa7++EuzCQiIjHI5p62Xzaz\nxcDIaH4D3N3PiDOYiIjkVjYFfzmZIZwa4LN444iISFyyKfi/c/efxJ5ERERi1dpROsXR02fN7E7g\nKeBQw3R33xZzNhERyaHWevj/65jXpU2eO/CV3McREZG4tHaUzrSuDCIiIvFqcwzfzP6umbd/B9S4\ne23uI0ku/WL1PezetpWevXozcMjpXLpgMX1O6J90rNRJw3pURmlLNpdWKAX+EhgWPb4DfA140Mz+\nPsZskgPDx1/A1bc/zlW3PcagoSOpqXgo6UiplIb1qIzSlmyO0jkdKHb3jwDM7PvA08BUModq3hFf\nPGmP6vLl1FdtoN+AkzjxS0MZPGocxTO+1Th9yOjxvPXS5gQTpkMa1qMySkdk08MvoMnROcBhYIi7\nHzzmfUnQ/t317HxhE1feuporFt7L/l2vfmGe+ucqGFk0JYF06ZGG9aiM0lHZ9PAfAV40s/XR6yuA\n1WZ2AvBabMmkXd59fTtnTppG7z59ASgsvvio6dXly+nRsydjp1yeRLzUSMN6VEbpqDYLvrv/0Mx+\nAjT8Kv5Ld6+Ons+LLZnkTP1zFezeXsXsW36MmSUdJ7XSsB6VUVrT4pCOmQ2Ifp4M7AL+b/TYFb3X\nKjM73sxeMrNXzOxVM/unXIWWLzpt3Pnsqt7CkU8/4dODH7Nn21YA9r7yS7ZtWMXMG+5u7G1Jy9Kw\nHpVROqq1Hv5qYCaZL2ad6KJpTX62dfG0Q8BX3P0jM+sNPG9mP3H3X3U+thyrYNTZjJl8GY/efBX9\nBpxEwRnnALB15e18dvgw65dcC8CQ0ecxbf4tSUbNa2lYj8ooHdXaiVczo5+jOtKwuzvwUfSyd/Tw\njrQl2SmdPZ/S2fMBeHHtAwBcc9f61j4izUjDelRG6YhsTrwyMmP1o6Lx/BHAUHd/KYvP9iTzF8Jo\n4H53f7GZeRYACwBGjBjRzvhhq6x7r8VpH75/AOt9hH2tzANwxYRTcx0rlVpal/m0HpVROiubo3T+\nBfgjmWvn/JDMHa/WApPa+qC7fwZMNLNBwDozG+/uO46ZZxmwDKC0tFR/AeTIoIv0fXoupGE9KqNk\nK5vj8C9w978CPgFw998Cx7VnIe7+IfAsmTN0RUQkAdkU/MPR0IwDmNlgMj3+VpnZ4Khnj5n1BaYD\nr3ciq4iIdEI2Qzr3AuuAAjMrA74J/GMWnzsVWBn9sugBPO7uGzqcVEREOiWbE68eMbMa4FIyh2TO\ndvf6LD5XB5zf+YgiIpIL2fTwAX4N/L5hfjMb4e7/EVsqERHJuWwOy/wu8H3gfTI3MW848WpCvNFE\nRCSXsunhXw+c5e7/L+4wIiISn2yO0nmbzB2uREQkxVrs4Te5teEuYIuZPU2T69+7+10xZxMRkRxq\nbUin4UaT/xE9jqOdJ1yJiEj+aO3iabqcsYhIN5LNGL6IiHQDKvgiIoFos+A3d3crM+vQNfJFRCQ5\n2fTwKxtudwhgZucAlfFFEhGROGRT8G8lU/RPNLMS4Angz+ONJSIiuZbNxdOeju5J+1Myh2rOcfed\nsScTEZGcau3Eq//N0fegHQi8BVxnZrj7X8cdTkREcqe1Hn71Ma9r4gwiIiLxau3Eq5UAZnYC8El0\nf9qGG5P36Zp4IiKSK9l8absZ6NvkdV/g5/HEERGRuGRT8I93948aXkTP+8UXSURE4pBNwf/YzIob\nXkSHZh6ML5KIiMQhmxug/A3whJm9S+ZuV0OBubGmEhGRnMvmOPyXzWwccFb01hvufjjeWCIikmvZ\n3sT8LOAc4HigODoOf1V8sUREJNeyuYn594FLyBT8Z4DLgecBFXwRkRTJ5kvbbwKXAv/p7t8Gisic\ndSsiIimSzZDOQXf/o5kdia6auR8YHnOuIC37n//Er7b8jF69e3Pa8ELOmfsP9Dmhf9sflFRq2N5/\nOAIDh5zOpQsWa3t3wMKFC6msrOS4447jzDPP5KGHHmLQoEFJx8pL2fTwq81sEPAgmcsrbANeiDVV\noIovvJgHy7ewbN2zDBt5BjUVDyUdSWLUsL2vuu0xBg0dqe3dQdOnT2fHjh3U1dUxduxYlixZknSk\nvJXNUTrXRk+XmtlGYIC718Ubq/srKytj5cqVFBQUMHz4cEpKSij9+jWN088uKqH2sccTTCi5VF2+\nnPqqDTx76lAGDz2NsedO4M++fW3j9CGjx/PWS5sTTJgO1eXLWXfLRgadfErjenzgzs9vvz158mSe\nfPLJBBPmt2zueNX4v9Dd97h7XdP3pP1qampYs2YNtbW1PPPMM7z88stfmGfTU48ysmhKAukk1/bv\nrmfnC5u48tbVlC19hJ07ar8wT/1zFdrebWhYj0vX/rzF9bhixQouv/zyBNKlQ2uXRz6ezCUUTjGz\nk8icdAUwABjWBdm6raqqKubMmUO/fpkrVMyaNeuo6Y88cA89e/Vi7BT9x+0O3n19O2dOmkbvPn05\n4cT+XDjtT4+aXl2+nB49e2p7t6FhPR7fN7PfHLsey8rK6NWrF/PmzUsiXiq0NqTzHTJn2Z5GZuy+\noeD/Hrgv5lzB2rRuDS8+9zPuWP4Em974bdJxJGab1q1h9/YqZt/yY8ys7Q9Isx5++GE2bNjA5s2b\ntR5b0eKQjrv/s7uPAm509zPcfVT0KHL3Ngu+mQ03s2fN7DUze9XMrs9p8hSbOnUq5eXlHDx4kAMH\nDlBZmblF8MtV/8bjK+7nB/etbOzFSPqdNu58dlVv4cinn/CHjz/ihS0/BT7f3jNvuJveffq20Yo0\nrMdDnxw8aj1u3LiRO+64g4qKisa/mqV52RyW+Z9m1t/dD5jZPwLFwI/cfVsbnzsC3ODu28ysP1Bj\nZj9z99c6GzrtiouLmTt3LkVFRRQUFDBp0iQA7iu7hcOHP+Uf/iJzqaK+w8Yxbf4tSUaVHCgYdTZj\nJl/GozdfRdWpQzlr/ETg8+29fknmy9sho8/T9m5Fw3r8zn+5lEEnn9K4Hq+77joOHTrE9OnTgcwX\nt0uXLk0yat7KpuB/z92fMLOLgK8CdwI/Bi5o7UPu/h7wXvT8gJnVkxn7D77gAyxatIhFixYBsHjx\nYgBWbvzVUfOsr93X1bEkJqWz51M6ez7fmDiMVfffCXy+vbWds1c6ez4/XPw/ABrX45tvvplkpFTJ\n5jj8z6KfM4Bl7v40cFx7FmJmhcD5wIvt+ZyIiOSOuXvrM5htAPYB08kM5xwEXnL3oqwWYHYi8BxQ\n5u5PNTN9AbAAYMSIESV79+5t1z8gTQpverpTn99z24yctpeWNpUxN22mMWNcbXYnZlbj7qXZzJtN\nD/+/AZuAP3X3D4GTgYVZBukNrAUeaa7YA7j7MncvdffSwYMHZ9OsiIh0QDZn2v4BeKrJ68ax+dZY\n5tio5UC9u9/VmZAiItJ52fTwO2oKcA3wFTOrjR5fj3F5IiLSimxvgNJu7v48n5+sJSIiCYuzhy8i\nInlEBV9EJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQ\nwRcRCYQKvohIIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVE\nAqGCLyISCBV8EZFAqOCLiARCBb8TFi5cyLhx45gwYQJz5szhww8/TDqSiHRSd96vVfA7Yfr06ezY\nsYO6ujrGjh3LkiVLko4kIp3UnffrXkkHSIuysjJWrlxJQUEBw4cPp6SkhBtvvLFx+uTJk3nyyScT\nTCgi7RXafq2Cn4WamhrWrFlDbW0tR44cobi4mJKSkqPmWbFiBXPnzk0ooYi0V4j7tQp+Fqqqqpgz\nZw79+vUDYNasWUdNLysro1evXsybNy+JeCLSASHu1yr4nfTwww+zYcMGNm/ejJklHUdEcqC77tex\nfWlrZivMbL+Z7YhrGV1l6tSplJeXc/DgQQ4cOEBlZSUAGzdu5I477qCioqKxlyAi6RDifh1nD/9h\n4D5gVYzL6BLFxcXMnTuXoqIiCgoKmDRpEgDXXXcdhw4dYvr06UDmC56lS5cmGVVEshTifh1bwXf3\nrWZWGFf7XW3RokUsWrQIgMWLFwPw5ptvJphIRDortP068TF8M1sALAAYMWJEwmk+V3jT0y1O+/D5\nnVjvvtz3QcvzAOy5bUauY4lIJ7W0b2e7X0N69+3EC767LwOWAZSWlnrCcbIy6KLu8629iGSEsF/r\nTFsRkUCo4IuIBCLOwzIfBV4AzjKzd8xsflzLEhGRtsV5lM5VcbUtIiLtpyEdEZFAqOCLiARCBV9E\nJBAq+CIigVDBFxEJhAq+iEggVPBFRAKhgi8iEggVfBGRQKjgi4gEQgVfRCQQKvgiIoFQwRcRCYQK\nvohIIFTwRUQCoYIvIhIIFXwRkUCo4IuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8EVEAqGCLyIS\niGAK/hNPPMG5555Ljx49qK6uTjqOiATke9/7HhMmTGDixIlcdtllvPvuu4nkCKbgjx8/nqeeeoqp\nU6cmHUVEArNw4ULq6uqora1l5syZ/OAHP0gkR69ElhqzsrIyVq5cSUFBAcOHD6ekpIQbb7wx6Vgi\nEoC26s/HH3+MmSWSrdsV/JqaGtasWUNtbS1HjhyhuLiYkpKSpGOJSABaqz+LFi1i1apVDBw4kGef\nfTaRfN1uSKeqqoo5c+bQr18/BgwYwKxZs5KOJCKBaK3+lJWV8fbbbzNv3jzuu+++RPJ1u4IvIpLP\n5s2bx9q1axNZdqwF38y+ZmZvmNmbZnZTnMtqMHXqVMrLyzl48CAHDhygsrKyKxYrItJi/fn1r3/d\nOM/69esZN25cIvliG8M3s57A/cB04B3gZTOrcPfX4lomQHFxMXPnzqWoqIiCggImTZoEwLp16/ju\nd7/Lb37zG2bMmMHEiRPZtGlTnFFEJDAt1Z+bbrqJN954gx49ejBy5EiWLl2aSL44e/hfBt50913u\n/imwBvhGjMtrtGjRInbu3Mnzzz/P2LFjAZgzZw7vvPMOhw4d4v3331exF5FYNFd/1q5dy44dO6ir\nq6OyspJhw4Ylki3Ogj8MeLvJ63ei90REJAHm7vE0bPZN4Gvu/hfR62uAC9z9umPmWwAsiF6eBbwR\nS6DsnQJ8kOdtpiFjHG0qY362l5Y205CxI0a6++BsZozzOPx9wPAmr0+P3juKuy8DlsWYo13MrNrd\nS/O5zTRkjKNNZczP9tLSZhoyxi3OIZ2XgTFmNsrMjgOuBCpiXJ6IiLQith6+ux8xs+uATUBPYIW7\nvxrX8kREpHWxXlrB3Z8BnolzGTGIY3gp122mIWMcbSpjfraXljbTkDFWsX1pKyIi+UWXVhARCYQK\nvuQ9Mys0sx352l5cbaaBtk26qOCLiARCBT9GZlZuZjVm9mp0glkQbcaREehlZo+YWb2ZPWlm/fKs\nvZy3mYZtHQlu26SWu+sR0wM4OfrZF9gBfCmENmNorxBwYEr0egVwY760F2ObadjWQW6btD7Uw4/X\nX5vZK8CvyJx1PCaQNuPI+La7/yJ6/q/ARXnWXhxtpmFbQ5jbJpW63S0O84WZXQJ8FbjQ3f9gZluA\n47t7m3FkjBx7/HBnjyfOdXs5bTMN27qJoLZNmqmHH5+BwG+jHWscMDmQNuPICDDCzC6Mnl8NPJ9n\n7eW6zTRs6wahbZvUUsGPz0YyXxTVA7eR+RM6hDbjyAiZq6j+VdTuScCP86y9XLeZhm3dILRtk1o6\n01ZEJBDq4YuIBEIFX0QkECr4IiKBUMEXEQmECr6ISCBU8CWVzOyXMbRZaGZXt/Mzt7Qx/RkzG9S5\nZCK5ocMyRSLRmag3uvvMdnzmI3c/sZn3jcz+9cccRhTpFPXwJZXM7KPo5yVmtiW6AuLr0RURLZq2\nx8zuMLN/N7OXzGx09P7DZvbNY9siczLSn5hZrZn97THLO9XMtkbTdpjZn5jZbUDf6L1Hor8Q3jCz\nVWQuTDY8ynBKNK3ezB6MrlT5UzPrG7U9yczqonbuNF27XWKigi/dwfnA3wDnAGcAU5pM+527nwfc\nB9zTRjs3AVXuPtHd7z5m2tXAJnefCBQBte5+E3Awmn9eNN8Y4F/c/Vx333tMG2OA+939XOBD4L9G\n7z8EfCdq+7Ms/80i7aaCL93BS+7+TjR8UkvmcrgNHm3y88JjP9gOLwPfNrPFwHnufqCF+fa6e0uX\nLNjt7rXR8xqgMBrf7+/uL0Tvr+5ERpFWqeBLd3CoyfPPOPoqsN7M8yNE//fNrAdwXFsLcPetwFRg\nH/CwmX2rhVk/7mBOkdip4Et3N7fJz4Ze9B6gJHo+C+gdPT8A9G+uETMbCbzv7g8C/wcojiYdNrPe\nzX0mG+7+IXDAzC6I3rqyo22JtEUFX7q7k8ysDrgeaPgi9kHg4uhGIBfyea+8DvjMzF459ktb4BLg\nFTPbTuaXxz9H7y8D6szskU5knA88aGa1wAnA7zrRlkiLdFimdFtmtgcodfcPks7SGjM70d0bjjq6\nCTjV3a9POJZ0QxpDFEneDDO7mcz+uBf478nGke5KPXwRkUBoDF9EJBAq+CIigVDBFxEJhAq+iEgg\nVPBFRAKhgi8iEoj/Dyszj04/2MxtAAAAAElFTkSuQmCC\n", "text/plain": [ "" ] }, "metadata": {}, "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", "## The construction, more concisely\n", "\n", "The PDA to CFG construction does this, but not for a particular string; it does this for all possible strings. As mentioned above, although the construction is challenging to understand, it's quite easy to actually carry out. The only problem is that the book's version generates a lot more rules than are usually necessary. \n", "\n", "Before beginning, preprocess the PDA so that it has the properties listed on page 121. If we ever ask you to run this construction, we'll give you a PDA so that it already has these properties.\n", "\n", "1. For each pair of push/pop transitions $p \\xrightarrow{a, \\varepsilon \\rightarrow u} r$ and $s \\xrightarrow{b, u \\rightarrow \\varepsilon} q$, create the rule $A_{pq} \\rightarrow a A_{rs} b$.\n", "2. For each triple of states $p, q, r$, create the rule $A_{pq} \\rightarrow A_{pr} A_{rq}$.\n", "3. For each state $p$, create the rule $A_{pp} \\rightarrow \\varepsilon$.\n", "\n", "The start symbol is $A_{q_0,q_{\\text{accept}}}$.\n", "\n", "If your PDA has $n$ states, then step 2 above generates $n^3$ rules, and step 1 generates $n^4$ rules in the (rarely attained) worst case. To avoid generating so many rules, remember that a nonterminal $A_{pq}$ should only be generated if it's possible for the PDA to get from state $p$ to state $q$ starting and ending with the same stack. Any rules involving impossible nonterminals should not be created.\n", "\n", "For example, with the above PDA, nonterminals $A_{q_2,q_1}$, $A_{q_3,q_2}$, and $A_{q_3,q_1}$ are impossible because there aren't any paths from $q_2$ to $q_1$, etc. And $A_{q_1,q_2}$ is impossible because the only path that gets from $q_1$ to $q_2$ changes the stack, and similarly for $A_{q_2,q_3}$.\n", "\n", "\n", "## Example construction\n", "\n", "Let's run the construction but remove all rules that can't be reached from the start symbol or that can't reach a string:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/html": [ "start: (start,accept)
\n", "(start,accept) → (q1,q3)
\n", "(q2,q2) → a (q2,q2) b
\n", "(q1,q3) → (q2,q2)
\n", "(q1,q1) → (q1,q1) (q1,q1)
\n", "(q1,q3) → (q1,q1) (q1,q3)
\n", "(q1,q3) → (q1,q3) (q3,q3)
\n", "(q3,q3) → (q3,q3) (q3,q3)
\n", "(q2,q2) → (q2,q2) (q2,q2)
\n", "(q1,q1) → ε
\n", "(q3,q3) → ε
\n", "(q2,q2) → ε" ], "text/plain": [ "" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "to_grammar(mc).remove_useless()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Even after removing useless rules, there are still some that don't really need to be there; but hopefully it's clear that the grammar generates the right language. \"start\" and \"accept\" are the names of states that were added to the PDA during preprocessing." ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 1 }