{ "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": [ "" ], "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": [ "" ], "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": [ "" ], "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": [ "" ], "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": [ "" ], "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": [ "