{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 4: Non-regular languages" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from tock import *\n", "from tock.syntax import String\n", "import itertools" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Tuesday\n", "\n", "
Read Section 1.4, focusing on pages 77-79.
Watch W4E2: The Pumping Lemma.
\n", "\n", "Alice first chooses $s = \\texttt{0}^p \\texttt{1}^p$, which she knows belongs to $B$. Hopefully it will become clear soon why she chooses this particular string.\n", "\n", "Alice knows that Bill's DFA $M$, which supposedly recognizes $B$, has $p$ states. And on reading the first $p$ symbols, this automaton must make $(p+1)$ visits to states: first the start state, then one for each symbol. By the [pigeonhole principle](https://en.wikipedia.org/wiki/Pigeonhole_principle), two of these visits must be to the same state. So when she asks Bill whether this happens, she knows that the answer must be yes.\n", "\n", "Now let $x$ be the part of the string read before the first visit, let $y$ be the part of the string read between the two visits, and let $z$ be the part of the string read after the second visit. Alice knows that $y$ is nonempty because $M$ is a DFA, and $|xy| \\leq p$ because the repeat must occur within the first $p$ symbols. Her choice of $s$, then, guarantees that $y$ consists of one or more $\\texttt{0}$'s and no $\\texttt{1}$'s.\n", "\n", "Here's what the accepting path for $s$ looks like:\n", "![image.png](attachment:image.png)\n", "The dashed line stands for one or more transitions. By going around the loop zero times, we get an accepting path for $xz$; by going around the loop two times, we get accepting path for $xyyz$; and in general, by going around the loop $i$ times, we get an accepting path for $xy^iz$. So all of these strings must be accepted by $M$.\n", "\n", "Alice chooses one of these strings. In this case, the choice doesn't matter too much; she chooses $i=2$. But because $y$ consists of one or more $\\texttt{0}$'s and no $\\texttt{1}$'s, $xyyz$ has more $\\texttt{0}$'s than $\\texttt{1}$'s and therefore does not belong to $B$. \n", "\n", "Since $M$ accepts $xyyz$ but $xyyz \\not\\in B$, $M$ does not recognize $B$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The dialogue becomes a proof\n", "\n", "Now we distill the dialogue into a proof.\n", "\n", "Claim: The language $B = \\{\\texttt{0}^n \\texttt{1}^n \\mid n \\geq 0\\}$ is not regular.\n", "\n", "Proof: Suppose, for the sake of contradiction, that there is a DFA $M$ that recognizes $B$. Let $p$ be the number of states in $M$. Let $s = \\texttt{0}^p \\texttt{1}^p$, which belongs to $B$, so is accepted by $M$. On reading the first $p$ symbols of $s$, $M$ makes $(p+1)$ visits to states (the start state plus one for each symbol). But $M$ has only $p$ states, so by the pigeonhole principle, it must visit the same state $q$ twice while reading the first $p$ symbols. \n", "\n", "Let $x$ be the string read before the first visit to $q$, let $y$ be the string read between the first two visits to $q$, and let $z$ be the rest of the string. We know that $y$ must be nonempty because $M$ is a DFA, and $y$ must contain only $\\texttt{0}$s, because the repeat visit to $q$ occurred within the first $p$ symbols of $s$.\n", "\n", "So $xyyz$ has more $\\texttt{0}$'s than $\\texttt{1}$'s, so it does not belong to $B$. But $M$ must accept $xyyz$. This contradicts the assumption that $M$ recognizes $B$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The pumping lemma\n", "\n", "If you were to write more and more of these proofs, however, you would find yourself making the same argument over and over. The pumping lemma is like a boilerplate non-regularity proof that you can use to simplify your proofs.\n", "\n", "The lemma itself goes like this:\n", "\n", "1. For all regular languages $A$,\n", "2. there exists a $p \\geq 1$ such that\n", "3. for all $s \\in A$ such that $|s| \\geq p$,\n", "4. there exist $x, y, z$ such that $s = xyz$, $|y| > 0$, $|xy| \\leq p$ and\n", "5. for all $i \\geq 0$, $x y^i z \\in A$.\n", "\n", "And here is how you use it:\n", "\n", "Claim: The language $B = \\{\\texttt{0}^n \\texttt{1}^n \\mid n \\geq 0\\}$ is not regular.\n", "\n", "Proof: Suppose, for the sake of contradiction, that $B$ is regular. By the pumping lemma for regular languages, there is a $p \\geq 1$ such that any $s \\in B$ such that $|s| \\geq p$ can be written as $s = xyz$, where $|y| > 0$, $|xy| \\leq p$, and for all $i$, $x y^i z \\in B$.\n", "\n", "Let $s = \\texttt{0}^p \\texttt{1}^p$ (line 3). Then the pumping lemma writes $s$ as $xyz$, where $|y| > 0$ and $|xy| \\leq p$ (line 4), which means that $y$ consists of one or more $\\texttt{0}$'s. Let $i=2$. The pumping lemma says (line 5) that $xy^iz \\in B$, but $xy^iz$ contains more $\\texttt{0}$s than $\\texttt{1}$s, which is a contradiction.\n", "\n", "The advantage is that this proof is shorter and doesn't need to make reference to an actual automaton. If you prefer to use the longer form, it's fine with me. But, regardless, you need to understand the argument, and it's critical that you remember which variables you get to choose and which variables you don't get to choose. Your job, as Alice, is to choose $s$ (line 3) and $i$ (line 5), and to produce a contradiction, namely, that $xy^iz$ does not belong to the language. Bill chooses $p$ (line 2) and $xyz$ (line 4); since you don't get to choose them, you must write your argument to work for any values of $p$ and $xyz$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## More practice with the pumping lemma\n", "\n", "**Question.** Prove that $G = \\{ ww^R \\mid w \\in \\{\\mathtt{0},\\mathtt{1}\\}^\\ast\\}$ is not regular.\n", "\n", "**Question.** Prove that $C = \\{w \\in \\{\\mathtt{0}, \\mathtt{1}\\}^\\ast \\mid \\text{$w$ contains an equal number of $\\mathtt{0}$'s and $\\mathtt{1}$'s}\\}$ is not regular." ] }, { "attachments": { "image.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnIAAABSCAYAAADQHTmKAAAAAXNSR0IArs4c6QAAAJBlWElmTU0AKgAAAAgABgEGAAMAAAABAAIAAAESAAMAAAABAAEAAAEaAAUAAAABAAAAVgEbAAUAAAABAAAAXgEoAAMAAAABAAIAAIdpAAQAAAABAAAAZgAAAAAAAACQAAAAAQAAAJAAAAABAAOgAQADAAAAAQABAACgAgAEAAAAAQAAAnKgAwAEAAAAAQAAAFIAAAAA7jOKIAAAAAlwSFlzAAAWJQAAFiUBSVIk8AAAAgtpVFh0WE1MOmNvbS5hZG9iZS54bXAAAAAAADx4OnhtcG1ldGEgeG1sbnM6eD0iYWRvYmU6bnM6bWV0YS8iIHg6eG1wdGs9IlhNUCBDb3JlIDUuNC4wIj4KICAgPHJkZjpSREYgeG1sbnM6cmRmPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjIj4KICAgICAgPHJkZjpEZXNjcmlwdGlvbiByZGY6YWJvdXQ9IiIKICAgICAgICAgICAgeG1sbnM6dGlmZj0iaHR0cDovL25zLmFkb2JlLmNvbS90aWZmLzEuMC8iPgogICAgICAgICA8dGlmZjpPcmllbnRhdGlvbj4xPC90aWZmOk9yaWVudGF0aW9uPgogICAgICAgICA8dGlmZjpQaG90b21ldHJpY0ludGVycHJldGF0aW9uPjI8L3RpZmY6UGhvdG9tZXRyaWNJbnRlcnByZXRhdGlvbj4KICAgICAgICAgPHRpZmY6UmVzb2x1dGlvblVuaXQ+MjwvdGlmZjpSZXNvbHV0aW9uVW5pdD4KICAgICAgICAgPHRpZmY6Q29tcHJlc3Npb24+NTwvdGlmZjpDb21wcmVzc2lvbj4KICAgICAgPC9yZGY6RGVzY3JpcHRpb24+CiAgIDwvcmRmOlJERj4KPC94OnhtcG1ldGE+Cs+OiooAADFwSURBVHgB7V0J/BVTG542pZKktGpTKYlCaFP25aOP9KEFfSgqpAilT1GWLCURkSSEJCEipM2uCKWNFi2WlKi03vM9z3HP3+l2t7l35t65///7/n7PnbkzZ87yvHPOvGd3HBFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBoQBYUAYEAaEAWFAGBAGhAFhQBgQBgoqAych4f2Bx4EhwH4ApQfwNXAZ/7iQcXDL545w8Yw49YYB0aU3PIovwoAwIAyQASlT5T0IPAMDEENl4XecFwJqAVuBP4AKgBtpC8f0c7qbh8Rt2gyILtOmUDwQBoQBYSCPASlT86iQk6AyUB0R2wPQ6FoGPAjcCFCmAbzOFzkV+QQP8fl/p/KwPOOaAdGla8rkAWFAGBAGYjIgZWpMauRGkBi4BZGhsbUZOMSK2LHh61twLG1dd3NKA45+z3PzkLhNmQHRZcrUyYPCgDAgDOzDgJSp+1AiF4LIwDuIFI2tCRGRGxe+/lzEdTd/Oc7ut7A/rdw8KG5TYkB0mRJt8pAwIAwIA1EZkDI1Ki1yMQgMlEMkXg1jG4405BaH/w/E8UBgO8DrZwOR0hwXXgT4DFvsfgHY6sYu2JKALaPxh/68ZF+Uc88YEF16RqV4JAwIA8KAI2WqvAQ5wcDpiCWNq2gYievnWfcOwrkt/8OfaM+ZazNtxzi/POyeXbdFI+7J3/QZEF2mz6H4IAwIA8KAYUDKVMNEjhz9NixKgIe6YdTGsSzA8WbFAbaE/QlsADjJgFgB0CDyW75HAF2BM4H2AFvfrgMonwJdeAKh8bVJn/39cw4Od4b/z8LxAWAJUBG4FfgX0BqoD7C1jsI0UcoATYGP+SfHhANe6wF1AKaVOiR2AmyRJE9MJ3W4FKBuMyWiy+SYZiszdcj8WAPg+0gdFgGoQ2ItsBygDtcDIsKAMOA9A5XgpcmLVXB+AMC8uAdgPuR3cRVgylOuopBJkTI1MdvsebNtG5av1CGHU3GlC+rxZ8DYNtRnTkkzxPYuYA6wA1AusBFuXwN6AzUBv+VRBMD4fRgREP/z+lcR118OX2c3arGIe5XD9/gcW/SM0AgyHPQ1FwN+ZFp6AEwvX0YT/2SOu+CexvB9wMlAYSATIrrcm2W+n+cCbGFeAISAZPRn3LDgeRboAhwEiAgDwkBqDPAjfznwDLASMHksmSPz7TfAIwCXtKKhkCmRMvUfpgvhtDUwFGBjDL9zyejPuPkF7icB1wI03j0Vr1rkqiJW3YGOQC0Tw0KFCqnDDz/cqVu3rlOnTh3n4IMPdkqXLu0UL17c2bZtm/Pnn38669evd5YtW+YsWbLEWbt2LT8YfFmJBwESxpd/PMBWM6/lxLCHNDxsYY2JsuLvQ94vX2waN4sAKtIW4xevrbVurME53fLD6rkCrXDSPeW7cAnwX6ANkGeAVaxY0alfv77WY9WqVbUOqcedO3c6W7ZscTZt2uR8//33Wo/fffddkT179hyP5wkarusAjiccBbCm55cY/gu6LhuDYBrh7YE8Awx5Th1xxBFah7Vq1XLKli2r9VikSBGtQ+bF1atXGx1Sp6yAdA5jJ45vA2OAqQALJxFhQBiIzQA//GcDVwHnAMUBLcx7DRo00HmxevXqTpkyZXReRLmp8+LmzZudH374IS8vbt++/Ug8SPQE2Dr3CsDydD7gp0iZ+rc9w/K0A0A7RwvKTWW+iYcddphTrlw5rcP99tvP2bp1q7Zt1q1bp3W4ePFi56effqqABy8MYwSOs4GngReASFsClzIrdRHcU0Bey1u1atVUnz591Jtvvql+//135UZWrVqlxo8frzp27KhKlixptyD8jDBuAw4AvJL94REJ5Efp4ghP2bTN68MirvNvGeB0gJnqXuA54AuAzeJ85i8gstbE7ireex4ImrD7uxewCmAcFV7GULt27dSYMWMUjGw3KlQw7NT06dNVv379FIx37V/Y3904vgQcBXgtosu/V16nsZXH+dFHH60GDx6s5syZo3bs2JG0HkOhkPrmm2/UI488os444wxVuHBhOy8uRBiXA3mGvtfKFP+EgRxmgPmCFSC2oum8yPxz2mmnqYcfflgtWLBAMX8lK8y3c+fOVUOGDFFNmjTJy9thv9/F8WTADynoZSoN5wkAv1ua99q1a6tbbrlFvfPOOwoV32RVqN0tX75cjR07VrVv316hUm2Xpz/C/z4A+c64lEaIQwFtwPFFvfjii9WsWbNcvaTxmIBVq55//nnVtGlT++Vl686lHqW2Jfwxfte0/GRNyhBN49EIDZ7RQJ5icW6et4+0tCOF3cx0My3yRpb/t0X4bCXT8W/YsKE23twa4PH0+Nlnn6krrrhCFStWzHBKg/cxgDOjvJKCrMvqIJGtxFqHpUqVCrEitWjRonhqcXUPtUk1bNgwhdYD+z2fjzBbeKVA8UcYyAcMsAWLlXqdT9iocf/99yv0OrnKb/Eco3VH3XTTTeqAAw4w5SnDehWoCXgpBbVMZS/GSEB/54sWLRrq0qWL+vjjj+OpxdW9P/74Qxt1jRo1ssvTlQizHZAxOQUhsbtQoes0dOWVVyp0q7lKiFvHM2bMUM2bN7cTPRPhVwPSkZvwMP38OYonv4XvsfnaCGs/Jg4LcP4A0BU4DWBcvgR4/24gUpbgAu+xizEIcjAi8Rqg03PUUUep119/3TMjPJp+0W2ubrjhBsWMEQ53A45evbgFVZdsFd5KPmnA3XnnnQpdotHo9+Tarl27dIt5zZo1TT7gkZWbrNQmEa6IMBAEBljJfxTQZduhhx6qnn76aYWhJ57ku2iesLJ91113KQxxMeUpe4LYs+KVFMQylQ0bvwIKXaeh6667Tv3444/R6PfsGnsuI1paOXSF3bC+SRH4PATQXYgnnHCC+uKLLzxLUCKP2BzNbleM1zIvLo0tEp+qmFaM16N4sAjX+JEyLWgk1oR7RxT37GI29zkewha28G0H6B8t/WzLSYiANsQPPPDA0MiRI9Xu3bsT0e/ZfYyhU+xmQBwMWACyIExHCpouWWucDGgOO3TooNasWeOZjhJ5hPGtauDAgXYXwbeIS8N0FCjPCgM5ykB9xJsVez0k5bbbblPsTcqUYByW6ty5sylLeeT3jBX1dKUglakcvzgC0DyefPLJ6ttvv82UChXGRqrHHntMHXTQQcaGYM8jG8w8l5Lw8U1Aj5e54447dOAZS6kV0K+//qr+9a9/mReXCb85xdSyb5r+2N2nxivT+vZd+ML5Ybd0X8k4Ch9pqHHsG+/RyC0L2FIVf0x8+9k3wufFcFwK9Ixyz+tL/4WHuwDVsmVLhcHtFrOZPaUBybF4jAvwIVAOSFWyrUtOYnkaYAVgGcABrCzg/ZCa8FS38NIQnzRpUmYVZ4XGcXSYQGHe7T8RrzP8SLD4KQwElAF+bP8AOKlPffXVV1buyOzplClTbENgOeJ0WJqcZbtM5aQtfh86p5mORI/zez0L0MN/hg8fnlnFWaGx16pNmzamPN2NOHVLFHk392ndfwyo8uXLh2bPnm0Fnb1Tjj1g1y7jBQwDaFAlK/zwGsLYNRop/8MF3mdzNf1tFv7Pa/cA+wEUGmn8aBu/+PJHSktcMPdbR9wshf+Phe+zKdtPoRGp43HrrbdmtBUu1lvy5Zdfqho1ahhuFiJ+h6ZAQLZ1ydYxds9vA0aHwfdmI1Ad8FKOhmesrenm+JUrV8aiNmPX2fpgtQjsRNw6eZlg8UsYCCgDFyFeOwB1ySWX6EleGct0MQJixdwaU84y6ZgUuct2mcpodwX4bfCzpZ/p/JrhYDxjKJM9jDFUqBvIBgwYYL6JPN4OpC2cJTofUFiyQC1dujRW+Fm5PnHiRHsQPZtGk5V2cEiSaAgeGOUhDlo1ZFbGOVsk9Qc0fH0Ljswoxg0/2jxnixxbLgsDRlij4D12rxYPX6QhyOZ4fvyNH34actqIo+E7atSorOgqVqCshViDPpeDj4qAG8m2LgcgstThBVak24avsULglTSAR3rs5qmnnqo4YDZIwtlciB/BPHUJICIM5FcGLkTCWNbrFRrczEL1O89y1YAzzzzT5MVNiOORKSgh22Uqo8xKMb+z9reU172S8vBoCaB7FfweC+dW708++aS9WsDAdBJNY+M9JrRevXqezrxxm6h47t999127i+7WJBN8J9MFsCssmhTBRWO4mY9SM1zTisfRZJTfcf4wUBfYGr5ON7Y8jj90P826WBTn94XxKI6875chx+5U3Xr54osvxqMya/c4cNeqSc5DfFmBSFayrcsJiOivgN0iTIOdOh0PeCFs+V0FqLZt27paSiSTSr333ntNvtiBuEZr6faCC/FDGMgmA60R+HZAcXJREIWTLC688EKTFzke2m3PQLbLVOqX34HZPAkLW0B57SFzIY0je8I+BXTPxsaNG4OoRvXKK6/Yxly3VNP7FBNaqVKl0IoVKwKZUBMpjhOyullZW/JCTEvLVMszGniHAycBkZmjNK61AioARmgM/wYwU7GVJpqwBYr3/TDkGM9d9D9oLXFGd+bIsY+sMIS5IOe2YYS/aYmfujwVMWMN1pbj8YdpGWxfTPGcE0G+BPS4xr/++stQFsgjl0ZgXIE/AFZwRISB/MJAbSSElXd1/fXXBzL/mUhhEWHFQfuMK/ANsD/gpfhZprIizMrgsHCEr8WRLaCvA+wdS1cmwwPFdeG4tFKQhS1zjCuwG+C3xpV0hGu1//77h7I5gNMNwQ899JBJMJuTa7pKbXTH5XGZY51oCB0S3UnCq+xuY7x+AArHcO2XIcexjayNKY6JywVhhQErZIcYZ6AP4JVkSpeMLw35rwC+N15MeNAttjRy/VxaxKv3g91MXFMSaSfmA2Y4AU5FhIGcZaAYYv4ZoC644AJfl2ryKi9ihwh7MtKTHjPvZ5nalDwDtENYGeb5aKAIkK7QKFTYXSPkdrF7r/Ti1p/bb7/dlKfrEfekbZFacMzatF4c1m2g2XTPDMZ4Ax8BsQwn3Epa2P1J/4Yn/cQ/DtmixKZgPt8FiCV+GXKvIUDdipPJ5UXS1f8bb7xhdLgT8W8Si7QUrmdCl60RrxUAa49XpBDHyEfYiquHDnBiSK4Ix+9Zu3qYWnVk2uS/MJBLDNyLyCquoejlgul+52nOLC9RooSpHLf3mHC/ytTu5BqYGT5OwNELaQRPdLc4uy1zRbg8idW6+layRGgD4KKLLsqVdObFk33dXIwRCSW6JZvgOO4OwD1awVR+9Tjuot26BBcZj/ej3bSu+WHIaQOAy1Nkc4mRPMW4PGG3RZi7T3D0qovVT12ytv4AwAJzFXAykK6UhAf0S40YMcIlg9l3zhlgXFQT8WeXwNGAiDCQqwxw5uQu7mD0ySefZD9zuYwB1yhD/Im1AIcAeSV+lalPIYKM7zbgN+ALwAuZDU/UNddc45LB7DvneoFWb1VCg/wsJpTbfwS97zgWtRwvxzQAG4ByQLpyPjyYDvzXpUf3hJ+rk+A5rw25Egjve0BxrbZcFO5jV6VKFVOL7JKAPze3/dAlW34nA3znHgM4kNYL0V0Kxx57bNbWbEz33endu7fJiyxARYSBXGWAlXHVs2fPdLNEVp7ncIcTTzzR5MWhHivBjzJ1AeL4O9ASGAIw7o2AdEQPFzvkkENC7HLORRk9erTRISv4rOjHFBKoHnzwwVxMZ16cuTwD0wGwOTzo4rUhdwMSrLjtVi51qeYpL3wyYcIEo0OO89svwEq8nHwDN3oYR46D+AsIebnHXyTHfv9ngcmCE+kgP+cBIsJArjFwJiKsDj744FBQZzcmk4/ZQh6eEMhJBFUCrAROyuD4YjMkowHOWX6Y/zh1LUXxxEpAjRs3Lhm6AumGXays2DMdQF8gqpyNq6pq1aq+7hGXCYa4UTvTAtCqLwMEWbw05PjCrgYUx5p5JRzz9Nxzz2ls2LDBK28T+kNjlGkB3LaG4pGMyYcIieP5rgKuiMDx+J+KDMFD6vzzz0/IUbIOsqVDaxLS3FSIkGeEgSwzMAPhq/vuuy/ZrKbdZSu/xYskh0sxLQDHtgVVmiFijGMHK4Lzcf4zwCEsqUgnPKQaNGiQE5NU4unw7bffNjpchzRFbeD4gIl94IEH4vmTM/eswYE3paL5DD7jpSHXmTps2LChpy/sW2+9ZV6ejE7XpvHI9ACLMqgPN0EVguOtgIln5PF+N56F3bJrdiP99LI1Lls65AKl1h6CzVPgQx4RBrLFwHEIWJUpU8Z1d1y28lu8DzRb5ZgeYDMQ1AaO7uE41sHRCHs7GO9zzQWXR93TOHbs2Hj05My9xo0bGz2y4WAvqYl/qlSpUiHWJPKDTJ061SR24V4pzd9/9FiOMWPGeKrCQYMGaS6rV6/uqb+JPNu1a5duIea7CZyYv1WXlzo9lqNZs2aJ6HF1P1s6ZCT79etn8uITeamUE2Eg+Aw8giiqG2+80VVeo+Ns5rd4kW3durXJi12CT78nMTyGOqxYsWJgF1KPp69o98aPH290OMcwVDh8opsx0ZVTCBMdzL2cPmKbEqdChQpMwxHAUTmdmOQiXxnO2mAjetW+fcJJLcn5GHb1+eef67Pjj0+1p9BVcHmOixYt6mAfQ/Pfbmo31/LjUacT+5d6mrZs6ZCJuPTSS01a+GJG7Q4wDuQoDASEgaKIx0WMi/X+Jh21bOa3eJG0ypUCVZ6iW9nBtzEeNTlzr127dg7W+KUx1wKobkd8Hv4otmLlJ+nRo4exXDkDML9LTyRQQcmeqJArg3NdPo7TKl26tOaRLXL8n8np2/PmzTM65NT5/C6sRe3ksh3c6SJdCYoOmY6jjz7a6JEz40WEgaAzcAoiqMdVJZsPg5TfYsWZEzaKFSvGCUhcFuigoCvBg/itgB+eDlOJxW0mr6OBw5SnvQ1HZXGyB9ZqiC9ifpI333zTJDavCdIkOsvHegi/msdxeBn+ebaIM9dLon/RwE2ZMynYJs7Eg7wFRdia3RrgODmvRC//07x5c0/oDZIO+/fvb3Q41CuyxB9hIMwAeyMaeMyGXv6HW84lK0HKb/Hi3KZNG5MX23rMWbrenQQP2BLqldSER5xx7OmY8XjcZuqe1b36Gsnix6glj1hnplDx4sV5Ld9IixYtHEy55kvLPkGurxYUYW2Pa8FMBzgman8gXWEmcDAGIl1/9PM1atRwsM+bg82X9X8shulgHRt9beDAgZ6EkawnJ52kk0bneSfJPuujuyLweybANftISE0gXdHKs9Kbln9B0qH1XgZJh2nxKw8HhgFW8Dgh6lOgO+BFS5Pr8jRI+Q0cxBSrfPHmYxEzJNc3nsYT7HkZBngxHErrsFWrVrQDXEcmyA9Y5WkrxFMn7g6c6AHJflmTc+bMUX369FEYY8XFhvWxe/fuas2aNerTTz/V3XXssvNjooXVpXNCgBRzDTm3sBnnHAjeHEhFauAhPaDTax1Sb/T7yCOP9NrrpP3jzgaMAzAaCIpwKryJF48h4APgcoAzT1OR9/CQ50McgqBDLvKMtJGjHQCNYBFhwCsGWsMjvl8G3InnJeBsIJV3jR9GPRs9lbXjgpDf4hWu06dPNzzNRjqDJKwUm7jxOB+4HigPpCJ6ssr9998fj4607y1cuFDbMP/5z390yx/XqqOtg52VFLtA/ZJq1aoZruqSnAmAYlOdH8LlTNCaYwLc60jjgDOCGD5nlfgh1gbenZnYgEikIWfzsgRx7A+46Xo9De4VrHTPKWzZsqWO2xVXXOG538l6aBU8HwREf4xGNEPO6PFP3H8aaA24qQqugnu1fPnyZKlJyl0QdMiIWtvn1UI6RYQBrxhgPjN5j0dWGMz/dTgfCjQAkpWqcJjyNyko+S1W4cBtG5k+YH2yhGTInW3I2TrcifAnA20BN12v78C95xXjSF5HjRql+aQ9M2DAAMOtPvq5ucLpp59uwjqHXavamqtbVx/w1zu5/fbbHYwxcLBFiINNtB0squhgsV5nxowZTtu2bZ1vv/3WQUJ1gE2bNvUuYMsnK13eJ9AKx8NTdhPcBfCjPh3oCOwPxBNfdIidIZz581kpQt90hmes2om1dFjHvh6wc9tg436GXYCZQLJdr+z6PxQzdbkxN069kaDokKlhGRCWXMmLJr5yzC0G7LxYGVG/GXDT9ZpyeRqk/BZLZWjJ4axH3q4EsKwKitAwMWLrkMbbBQDHg60FhgFHAYkkZT0m8ti+b2Yof/fdd86QIUMcLOPmYEKgc/fddzv//ve/baeenlvfxbokiAvSOtjRwdNAYPVrw42eNmnSxHnnnXfMciA6HAy4dE455RRn5syZ+v8JJ/jT82mlS6dTB5YbP3yRTw/jDxxfAsYBHwGRcggvWGmNvJ/Sfxra27Zt089m05Cz0pVrOiR3tYBBwEBgFjAOmASw68YWrpVTCBM7HMxata+ndR4UHTIR/ICEJRf1aOIux9xkgEbC8WEMx5FGwTiAleU9gC36/bTKHfte3PMg5bdYEeV4scqVKzs//PADnTCtW2K5Dch126jjt653GF/iOA6YAGwAIsWX72JkIMaQwxZazmmnnea88MILTvnyqfYGR/oe+7/1fh7CFjltkWOJidhPpHDnzjvvdHbs2KHXbnnttdf2MuLoHV8ma40w31p8rHXxvE1gCpy4fMR+ecvg2a7Ah0C0rle9+J+VVpdBRXfO1lNKiRIlnEaNGkV3lIGrmC7vhCfiFENwuTwjpw3iPw74CXgaaA0YPev3M7/qEOl0rDIm1/Iioy+S2wyYfMZU7AdcBLwF/AgMBRoARvT7ab2v5nrCY1DKzEQRtcqZXM2LNMybACOAdcBkoC3AxikKbZuSnOxYsmTc/eW141R/tm7d6ixatEg/Xr9+fWfy5MkZMeIYoKXDA3wz5LAnmE7c5Zdf7mBsjD6P/LEX6POraxVLqphg9X5r+MMXINt4zEQqhWM9PHMXsAowXa809HSTLo9eiSmU2KLKxXmzKRiXYIKnQrOtP4a/00QoyaP9IWHh2QWYCZiu1zo4z9c6xNp4TCJlFLAZaMk/UeRMXGMrAXkWd/8QJLz8w4V95nZcjp0Xo3W9snXcrnjYYcU9D1KZGS+imzZtMre/wkkQylPG4TATqSSOtg75cboAeA1YCwwD+E4UQjcnbDnbKa56KBx6xKFjlP/973+2ceVhKNG9YhduWErRkNMfpJ073X6XjB/7HjH71Fm7lnxic7Rzz93XQfjKihUr9Bn7erEfY0x36dzgmIUCIJ7rkJyZQikZI7tXr14Od9PwS0xm8cv/APirX1RsS+ZpVBLpkN0B9957r4O163SFC3sUOy+/zCUJvZcCkhe9J058zDQDOhOm8k1MlN+YkHr16qU8dorlA59/9NFH0+KE+T6fS8o6dMOL6VblmEOzVJeb59Nxa72fO2nJsuZbCptbe9YasGzZsrz41apVK+888mTatGn6kp/jr9gtF5axOF5p/mT5yFmrqbbKLcWzzwDjgTUApSF/qEMvZfHixdq73377zWHG53g5qzlX32NL2aRJk5wnnnjCt+5XhgEjgDU2ShHAnOsLWfrhi+Wm9sM4m6ohFTUJGAfMBnivNuBgmQ4ePJNEOmSL+fPPP6+N8A4dOjivvPKKw+1snnrqKQczlT2LBz3CwpzGv6tw8pT5E+XI2WbJdPmIuyjk4VJB4+Xz6DTEvGrnxfVw9SwwDvgOoFzKn1TK00T57ffff3cwK93p2LEjg3Al7Mbj5EF+X//66y9Xz0Y6tspxdin/XdBHOsr8/+UIMtlWOVuHrARPBcYB7C43rTe7YOwUo/Fr2QG47Z0YQw57Y5vhP955nsAn6/3cUhhu2XXhWE2tCR5PfNt6SRzLatzrQdZcvvjiC33NT0POShcnDOSS8EU1wrg/CbQADgfuBowRh1NHp81KK6+lLVgHR/vBDz3HqJ111ll7+XnDDTfoQbP88Ftd2Hu58eLP5s36FaURRCvH5sUL7zPpx0wE1gWoBPwXmAWY9GRch/zoTJgwwaEBx6EQnFWOLdEcLAXkPPTQQ4iat2K9n1qh3vouvgkDcRkw+YyOWAGbCJwDHArcAhgjDqepfxMTlZnMX6yYHnfccQwnKeE3FOuh6nHmjz/+eFLPJHJk5cVc+y6apPF7wMkOvYAqQDvgdcAYcThNXY98OBkxhhw2VEjGuaduLB1upiG3gr6zluCV1KxZ0+FOABROdIgURqBr1655l/005L7//nsTjp6iY/7kwJEFz7tAJ4Af/m7AR0A00Wmz0hrNjetr99xzj2MKJrbIsTCxhf8vu+wyp2/fvnpGol9jEax06XfVjkMOnDPOg4DawMnAM8BWIFI24MKfzBtWBo104/p/PB1yujw/KlddxQayv6Vs2bJ64pHdqm7upXu0yphc1GO6yZfns8sAP/ycvdUD4Li4i4FpwB4gUvT7ab2vkfdj/o+X3/iQabwww1VWrlypV2/gCg6//PJLVH/5LeWwlWuvvdbB/uFR3bi5yJacn3/+mY9sB9giGXRRVgRJ0nCAH6NjgIcBlp3RROvR+n5Ec5PyNSwW7Ri//Vp1I17kTNhwo9M5Eidq2LBhKNO9k3POOYfkc8aImjhxol7xmN1js2fPVki0vsf7aPJUfu7xiunAJqyzEV5QhF2rJl6RxyW41x+o5iKyjemfH7svoFlarV+/XoP6iyXY9kWvZh3rfjrXMZ3bcOTP4C0XRFtOi5FzCxzxav6z5fBpoDXAD0iyMh8O9W4n6fAV+WwsHeJDpcaOHavs1evptnbt2urwww+P9Cat/xjjqMsCpg/Qk3OSJUXcCQMJGGA+43tlYOfFdbg+FGAXYrKyPxyG8G0KoQLr+r2Pld/oUfv27RVX5KcsWLBAYRkQhWUk1Ndff62vJfr56aefdBrT2a3gyy+/NDx9mywhGXLHVhcTN1uHbEGdDLQFigLJyvNwqJ555plEtKZ0H0uqmbjq72NKnqTx0DHHHGPCP56k6LmzZuHXZBlK5G7w4MHOe++9p8dVseuNLTtsseEYAVvYquPXHq/gyMFLa4JbaE4CePwDcXoJGAfEanXDrZiyFHd2o4WlCMZRcKZOTIdub3C2Ktc2y6awOyIsf8/zNv+Cd5yJKI0DJgHRWt1wOa7wHW3C9HrZSh1Lh4cddphDGGF+Yesq15diy4KXsmTJErMm4Vr4y/ddRBjwiwF++NkVNA6YDkRrdcPlmPIX7qyEQVaL68IdddRRMR1GuxErv9EtW+TYrYoGDb0oPtcC47CGWCs7RPM/3WtWeRrkbyIrwPx4jwMmALFa3XArpujvBdPLniOvxXSrVq9ePePfSA5lwrtpDLnF7P+cwwTOmjXL03TCWnQ+/PBDp0GDvytCHOdEI46LgsJCdho3ZiOSvzsGYA80hwP1IavD4HlQhDWOZLtOE8V5GxzMR+2x0Mcff5zIbc7dt95N/a4GLAErEJ9BQKKu02SirdPHQj7Twq4WrkLOsXHY99jB1nmeRiHgOvQ0reJZ1hj4DCGz7zFR12kyEfT8u7hhwwaHXalc0YFdpRyAP3fu3DwjDttk6nGqHKtq4MdMb6t8CWJ56qbrNJEePdehHSBaUfXfbHSrco4Bxk7S2GUkdMWYf2jter7Ho2k1hDGl8MKqNWvW6EtoNVKotWhrkhvM+iXWZuvPIn1BknqIjJuu02Tifj8cqX79+vlFZ1x//epahfGvsNMBjV7Wsr1rakyG0fhuWAlqDTD/eCX14ZFCC6geihCXcA9vTpkyRWElcoV1HRW2mFGpdCclio615zGHFYgIA14yQMPNTddpMmFfAUfqggsuSPRqJ30fLW+mBUV3r6KHSmGcU97zGJ+ad59hY5Z33j1z4kXXqrXnsbumxmRYS8/NSXjcTddpotCKw8F28ByCEW0ozBfHgQMHmndlhE3Cc/ijsDdYRhI5Z84cEwmFVZF9C7NFixYmnA52YvPp+cnUIfaz9I3PeB77ZchxDBfTBbyXT/UWmawfmF5sXRePbs/uoRVAYTC14ngLtGB75q/tEStuGCtLY5yoCYgIA0FnoCoiuAfDfkJYF9V+nVM+ZyUJfiosHKu++uqrvHPjIRs8bLASGynpGnIfffSRKU9/RFy8rIQGVZ9vkXPM9o2kMqf/o6fT6PFMm/hzmFg/BstHY+vBBx/UkShTpoxvLQ+rVq1iGPxwcM2uILXkIDq+CFuIOP5Iodk1Gu2+XvPLkLMmq7CGXBDkLiRSXX311b7qi56jO1VhqSDVunVrhXWpfAvPmqzyYUFQoKQx3zDwAfOiV4PlMWQhb6IDM1vDhg0Vxle5agFP15C77rrrjAHAHpyCIJ2RSF3G+VbAZdhjUwlAutgNXYRK5MefwrFaGziwExa7vuDnz6effqq956BPv5asGD16NMNgjYODXlMZeM7nc0lotL7ICHu11lC2E8/p/++//z4Lnh0AZy0VBOHAXq7vprhDip/CzZ25ADEnHHE9ObR+5oELA3sl4bxI73TavPJX/BEGfGZAv6/W+5tWcJzoYJYdoUedOnVyVq9e7cyYMSMtf5N9mAsKP/vssyxPKQUlL05BWrdhjK7ickv5QazvOydI7jOR505cVG3btvXdvuzevbs6/fTTfWvuxMdJYbwBDRu+tJlfqQ+BZkkOQ7i7OW0eA2p916MdAFvksCiifSnt827dupna4xNZ4jNbwb6PgNXQoUPT5jCeB5jJZfjd58hxNF4IKm3G701I0wHZIlTCFQZSYKAkntHjxzkcKB3BPsM6H9jDlzDxQXGcHPNhspJOi9zw4cNNXpyTAhe5/MgjiLzq0qVLsjQH1h17Udjdj/QQh0dTSgVc5OzHENe3yWXB3pHmhZ0VLaH5/BqtdIVdF3JZherHH3/k4Hu+rKxx1MvnOotM3hm4wEkPISzemdN6ZMWQaQHujkyk/BcGcoCBQYijwq42OZ0Psb2i7tZlWoBzgYIktZDY3ZhgGcL+7jmtx5tvvtmUp6/GU+Bw3Mzp/mQuXlu6dGnTGndavMTm03tHI117+NKiKTlnX1prluML+VRPiZL1CRxkbRayFy/O9OnTTaHDPuKKiRIs94WBADJwMOLExU/V1KlTvcgWWfHDmuU4H2kpCJMcIl+lZ6hDL2chZ1qR2G2HGyiY1rhjIxNo/y+LPxxApzhAORelc+fO5uMR12K1E50Pzx+jDjlRIBcFY0aMDjm28dB8qJ9kknQ8HIXYKrl06dKcU+OOHTtU/fr1jR5vSibB4kYYCCgDvRAvvSKAn5OC/MrkWODbdMcxP7YIKMd+R4tL1LBCqbgjQy6K2S0LaXgqGbI4O1AddNBBIXZv5ZK8/PLL5sPBlbnZnFpQhbVIPbZj5MiRuaRChX1GVY0aNYwe+xdUBYbTzQyrtz7D4o85pcfevXsbHXKEcbECrkdJfm4zwLXNvgFUz549cyofcruw5s2bm7z4bG6rIe3Ys0KpqlSpknPrymHCjdHhJqThkGSZeIMJbtWqlYq3v2aQ3mj2fWMbMNOl2iPZhOZjd+2oQ7bocG+9XJF27dqZF5Zdi14uDpmLqj4QkV5BPd500025okLdBcU4A1zEuSkgIgzkOgNNkABuMq8mT56cM3mxf//+pjxdjbiXy3UlpBl/LtXBiR7qvPPOyxkdciuuEiVKGNvmEjcclIfjNUzwNddcE/gEc+HERo0amRfWu3UT3DAWTLejqEO2cGV6FmsqL82gQYOMDjkmpWYwKc14rDjrehcQ8mo9q1R0k+wz33zzjV2hujHjbEmAwoB/DFwHr7n2Yk5UjsPrN9IA2A209I+WnPKZQ3V+AxSN3KALZyljP2zzXXwyFaab4yHOYlV33HFHYNPLMQtc+oLxBBYCHOcn8jcDJXDgIqwKGz+raCuFB0WxXHmb8QRY6BS0WVVIclzpibt6q7K33norKCrbJx5chLty5cqm5jgRcS6Ig6rjKlJu5jwDzyMFqmLFiiF7e619MkOWL7z77rtmYDzL1N45z7q3CeBuCKwcqyAPPeKOIk2aNDHfRS6+y+VwUpK2eIofVjV48OAsv5r7Bs/14rgeHeMH/AgU1IHxSHpMYXM6DVyFxSgV1zMKmtCI4354jCNwJSCyLwN34ZJuYg/i7DnOqKpdu7bJizMQ1+L7JkGuCAM5zwDHe04HdE/H4sWLg1acKu7pGt4Sj/mxoOzg4PbFugwPhPjdCaIxx63amjVrZsrTJYgre0nTki54WhtzPXr0cLWdiJ9vOBfGO/bYY01C1yOOR6SVyvz9MA3c5YCqV6+eCtJaOlZ3KnXZN3+rIe3U6a7yIkWKhLgHbVAEK9arChUqGEOcNccyaadUPBAGgstAaURN93RgY/sQF70OinDnBi49hfixPB0DSKs4SIghN+C65uq2224LigoVdvtQ1l6qKxDHmjHi7/ry+XiCM0HVKaecotatW5fVRM+ePVtVrVrVvKzLEK/arlNU8B6oiCTPA1S5cuVCb7zxRlZ1yNmp1sQGVhSkJS65d1LvwEI9cgbd9u3bs6rHJ5980h6IOw3xKgj7GienKXGVnxnYH4nTkwK50v6oUaOymg+53A8XgUecDO7Jz+R7mLbL4JfuZuXi5WwJy6ZMmzZNlS9f3tg2CxA3LpviqbSEbz8BOqApU6ZkPL38aHFhw8KFC5uEzkV8kp6K6ykbuenZAYj2VEBn9uuvv16xezrTwnXiavyzxAgnNsiYOHfvUzc41zPosE+q4ibKmZZffvlFXXTRReajweMTQEGfZexOi+I61xkoggQ8Cuh8wIopB6dnWjjB6JhjjjF5kTPFOaZWJHkGzoLTjYBuIOL4wkwL9sFVffr0oQ6NbfM2zrlqgS/CVp13AP3SnH322WrJkiUZSTPHBdWpU8e8rHsQhyEAM5KIOwbY1N4HYIbXa+pwg/ZMCNcltHZsoC65xEhNQMQ9A1wOgWMndMWGrXMbN270XY1cl2rEiBH2zNQ/EIcO7qMvTwgD+YaB/yAlrJDqGa3Dhg1TzCd+Cyev9erVS0+CYtgAh88cB4i4Z6A6HmHDkLYxLrzwQsXJW5mQl156SXFv63DYbB28BfC9S5wBXAtwYTr9EnXq1En5sT9rKBRSr776qj3oj4nlwownASLpMUBDgIaUfoE4q/W5557zpQDiQPhu3bqZvVMZ3lagPyAtOCAhDeFYneGA7hrgsgjci8+PoQ/cq/GRRx5RtWrVMgUOj28CMqwBJIgUeAZqgIHXAJ0/2OPw8MMPK7a0eC1s9evXr59dmeLQlIcBGZsKEtIQfo9oRP0J6Fm/V111lfJjQgvX5+XyMNasVL43nwMZN8QrINDRgP6I4KhatmypOFaA3S7pyMKFC9WAAQPsWXBM5K9AL0A+/iDBI6FR3gVYA+gCCGMP1Y033qjmzZuXjgr1UicckM9ZxdaMVLakvgDI7GKQ4KE0hF95LeXcj497Ck6cOFHRAEtV9uzZo2bNmqWuvvpqvdMLwtDvCI6LAekOBwkiwkAEA2fj/0JA55WyZcuGunbtqj744IO0Jgpyma1JkyYpthRxkXfjP47vAY0AEe8YqAqvngX4vdLfr1NPPVWNGTNG7zyUannK57g4f9++fe0WOL4n64CrgMJASuJF8x0/yuyqY0TYQuDgw60wdqcQ1ndzsOSFU7duXQfdog4G2fMenWiBVepgk3sHLTYOumidjz76yMGHw0EXnHHC40pgGPAUwHXtRLxnYD942QnoCzQw3leqVMmhDlu0aOFgFo3WIww9B4aCceLg3XQ2b97sYE0lrUcYgFqH8+fPZ8FllL0DD4wHHgCW5j0sJ14zwNrczUA7QA87QKGvTjzxRJ0XGzdurHWIVjUHrXd7hY3B0g5mS2kdoiLlzJ0715kzZ46DSSm2O85IHQqw5YEfExFhQBjYlwGWe20B5sXm5jaMOgeNHQ52THIaNmyo82L16tUdrNpvnOjjli1bHOyPqvPi119/rcvTTz75RCGPmvKUeW8KwLz4mX5IfvxgoA48vQm4HNBKwvh8jkfU5elxxx2ndYgFex3q1rZt0LXuoGdE6xAtero8xSRNbe9YEV2Cc34TaTTyGxkIKYVYdASmAnogNo6mBm+OoVKlSnHWJGe6mWvRjmx9ewJoA6RspeJZEfcMnIhHRgBrgWi64QbMWoelS5fmfbt2aLvfiXusLV4JlAVEMsdAJQTF1uuPAV2rxNHWDcfVqTJlyrCljV0Ie92LcLsM/+8CjgREhAFhwB0DXBZrMLAUiJrPmP+YD5kfsbRQVDd4luUsK1K9gSqASOYYOBBBdQGmA/yuRdNRiN9D2jb8PsZww+vrgZFAc8AzMRa+Zx6GPSqO4wnASQA/AHWB2gAJscNk3/4GgB8LgstjzAZM0zRORbLIQD2ETR02BXhOPXKWcDHACF/OLcAPAHW4CJgD0IjYCohklwEa0S3DqI8jdVgDYMXLFhZQbOKnDpcCHD/JvLgaEBEGhIH0GagGL1oDrCyb8rQKzvm9tGUb/qwCmBcXAx8CLFP3ah7Hf5HMM8DdFZoBrQAOaWGrHW0bdnFE2jY/4xp1SHwBsDylPj0XO2DPPY/iIcMjEXxx+bJuB0RyjwHqj4YAP/401mjMieQWA4UR3dJAEYCG+C5ARBgQBjLPACvGzItsPWd5yqNIbjFA24bfxP0A6jAwXaWIi4gwIAwIA8KAMCAMCAPCQFAZ+D/qqJWJSxd5AAAAAABJRU5ErkJggg==" } }, "cell_type": "markdown", "metadata": {}, "source": [ "# Thursday\n", "\n", "Reread Section 1.4, paying closer attention this time to pages 80-82.
\n", "