notes/week04/week04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 4: Non-regular languages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tock import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Monday reading\n",
    "\n",
    "Read Section 1.4, focusing on pages 77-79."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tuesday class\n",
    "\n",
    "## Non-regular languages\n",
    "\n",
    "We've seen that regular languages encompass all finite and cofinite languages, and three computational models (DFA, NFA, regular expression) turn out to recognize regular languages. Are there languages that aren't regular? Definitely -- the two classic examples are\n",
    "\n",
    "$$ B = \\{\\mathtt{0}^n \\mathtt{1}^n \\mid n \\geq 0\\} $$\n",
    "$$ G = \\{w w^R \\mid w \\in \\{\\mathtt{0}, \\mathtt{1}\\}^\\ast \\} $$\n",
    "\n",
    "The intuitive reason why is: If I give you two strings $u, v$, what information would you need about $u$ to decide whether $uv$ is in the language? Let's say that $L$ is the language of natural base-10 numbers that are divisible by 3. Recall that a number is divisible by 3 iff its digits sum to a multiple of 3. So the only information that you need about $u$ is the sum of its digits, _modulo 3_. That's a finite amount of information, so the language is regular.\n",
    "\n",
    "Now consider $B$. If I give you $u=\\mathtt{000001}$, the only $v$ that matches up with it is $v=\\mathtt{1111}$. The information that you need about $u$ is how many $\\mathtt{0}$'s it contains -- which can be unbounded. So, intuitively, this is not a regular language.\n",
    "\n",
    "## The pumping lemma\n",
    "\n",
    "But how do we really prove that $B$ is not regular? To do this, we entertain the possibility that it _is_ regular. If there were a DFA $M$ that recognizes $B$, we try to \"break\" it by finding a string that is _not_ in $B$ but _is_ accepted by $M$. If we show that we can break _all_ possible DFAs in this way, then that means we've shown that there is _no_ DFA that recognizes $B$. So $B$ is not regular.\n",
    "\n",
    "The way that we are going to find the string that breaks $M$ involves a back-and-forth that is best thought of as a dialogue. Below, we imagine a dialogue between two people named Alice and Bill. Bill proposes $M$. Alice gives Bill a \"test\" string $s$ that $M$ is supposed to accept. But then, she uses the information that Bill reveals to concoct another string, and this is the one that breaks $M$.\n",
    "\n",
    "## A dialogue\n",
    "\n",
    "Alice. The language $B = \\{\\texttt{0}^n \\texttt{1}^n \\mid n \\geq 0\\}$ is not regular.\n",
    "\n",
    "Bill. Yes it is!\n",
    "\n",
    "Alice. Oh really, then show me a DFA that generates it.\n",
    "\n",
    "Bill. Here's one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"67pt\" viewBox=\"0.00 0.00 144.00 67.00\" width=\"144pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g class=\"graph\" id=\"graph0\" transform=\"scale(1 1) rotate(0) translate(4 63)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" points=\"-4,4 -4,-63 140,-63 140,4 -4,4\" stroke=\"transparent\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\">\n",
       "<title>0</title>\n",
       "<path d=\"M53.3333,-21C53.3333,-21 43.6667,-21 43.6667,-21 40.8333,-21 38,-18.1667 38,-15.3333 38,-15.3333 38,-9.6667 38,-9.6667 38,-6.8333 40.8333,-4 43.6667,-4 43.6667,-4 53.3333,-4 53.3333,-4 56.1667,-4 59,-6.8333 59,-9.6667 59,-9.6667 59,-15.3333 59,-15.3333 59,-18.1667 56.1667,-21 53.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"42\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge1\">\n",
       "<title>_START-&gt;0</title>\n",
       "<path d=\"M1.0391,-12.5C4.1393,-12.5 19.9975,-12.5 32.5417,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"37.668,-12.5 32.6681,-14.7501 35.168,-12.5 32.668,-12.5001 32.668,-12.5001 32.668,-12.5001 35.168,-12.5 32.668,-10.2501 37.668,-12.5 37.668,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge2\">\n",
       "<title>0-&gt;0</title>\n",
       "<path d=\"M44.3279,-21.1857C42.0234,-29.6739 43.4141,-39 48.5,-39 52.5529,-39 54.2592,-33.0778 53.619,-26.3767\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"52.6721,-21.1857 55.7829,-25.7007 53.1207,-23.6451 53.5694,-26.1045 53.5694,-26.1045 53.5694,-26.1045 53.1207,-23.6451 51.356,-26.5083 52.6721,-21.1857 52.6721,-21.1857\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"45.5\" y=\"-44.8\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g class=\"node\" id=\"node3\">\n",
       "<title>1</title>\n",
       "<path d=\"M126.3333,-21C126.3333,-21 116.6667,-21 116.6667,-21 113.8333,-21 111,-18.1667 111,-15.3333 111,-15.3333 111,-9.6667 111,-9.6667 111,-6.8333 113.8333,-4 116.6667,-4 116.6667,-4 126.3333,-4 126.3333,-4 129.1667,-4 132,-6.8333 132,-9.6667 132,-9.6667 132,-15.3333 132,-15.3333 132,-18.1667 129.1667,-21 126.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<path d=\"M127.6667,-25C127.6667,-25 115.3333,-25 115.3333,-25 111.1667,-25 107,-20.8333 107,-16.6667 107,-16.6667 107,-8.3333 107,-8.3333 107,-4.1667 111.1667,0 115.3333,0 115.3333,0 127.6667,0 127.6667,0 131.8333,0 136,-4.1667 136,-8.3333 136,-8.3333 136,-16.6667 136,-16.6667 136,-20.8333 131.8333,-25 127.6667,-25\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"115\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g class=\"edge\" id=\"edge3\">\n",
       "<title>0-&gt;1</title>\n",
       "<path d=\"M59.2714,-12.5C70.4055,-12.5 88.0383,-12.5 101.6959,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"106.9001,-12.5 101.9001,-14.7501 104.4001,-12.5 101.9001,-12.5001 101.9001,-12.5001 101.9001,-12.5001 104.4001,-12.5 101.9,-10.2501 106.9001,-12.5 106.9001,-12.5\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"80\" y=\"-18.3\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g class=\"edge\" id=\"edge4\">\n",
       "<title>1-&gt;1</title>\n",
       "<path d=\"M115.1421,-25.0318C113.0721,-34.0334 115.1914,-43 121.5,-43 126.6257,-43 128.9859,-37.0807 128.5804,-30.0327\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"127.8579,-25.0318 130.7998,-29.6587 128.2154,-27.5061 128.573,-29.9804 128.573,-29.9804 128.573,-29.9804 128.2154,-27.5061 126.3461,-30.3022 127.8579,-25.0318 127.8579,-25.0318\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"118.5\" y=\"-48.8\">1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "m = read_csv(\"pumping1.csv\")\n",
    "m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice. How many states does it have?\n",
    "\n",
    "Bill. Let me see..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = len(m.states)\n",
    "p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice. Does your automaton accept the string $s = \\texttt{0}^p \\texttt{1}^p$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0', '0', '1', '1']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = [\"0\"]*p + [\"1\"]*p\n",
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bill. Of course..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"76pt\" viewBox=\"0.00 0.00 433.00 75.50\" width=\"433pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g class=\"graph\" id=\"graph0\" transform=\"scale(1 1) rotate(0) translate(4 71.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" points=\"-4,4 -4,-71.5 429,-71.5 429,4 -4,4\" stroke=\"transparent\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g class=\"node\" id=\"node3\">\n",
       "<title>1</title>\n",
       "<path d=\"M62.3333,-21C62.3333,-21 52.6667,-21 52.6667,-21 49.8333,-21 47,-18.1667 47,-15.3333 47,-15.3333 47,-9.6667 47,-9.6667 47,-6.8333 49.8333,-4 52.6667,-4 52.6667,-4 62.3333,-4 62.3333,-4 65.1667,-4 68,-6.8333 68,-9.6667 68,-9.6667 68,-15.3333 68,-15.3333 68,-18.1667 65.1667,-21 62.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"51\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;1 -->\n",
       "<g class=\"edge\" id=\"edge1\">\n",
       "<title>_START-&gt;1</title>\n",
       "<path d=\"M1.1401,-12.5C5.0617,-12.5 26.1734,-12.5 41.4077,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"46.7117,-12.5 41.7118,-14.7501 44.2117,-12.5 41.7117,-12.5001 41.7117,-12.5001 41.7117,-12.5001 44.2117,-12.5 41.7117,-10.2501 46.7117,-12.5 46.7117,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\">\n",
       "<title>0</title>\n",
       "<path d=\"M149.3333,-21C149.3333,-21 139.6667,-21 139.6667,-21 136.8333,-21 134,-18.1667 134,-15.3333 134,-15.3333 134,-9.6667 134,-9.6667 134,-6.8333 136.8333,-4 139.6667,-4 139.6667,-4 149.3333,-4 149.3333,-4 152.1667,-4 155,-6.8333 155,-9.6667 155,-9.6667 155,-15.3333 155,-15.3333 155,-18.1667 152.1667,-21 149.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"138\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g class=\"node\" id=\"node11\">\n",
       "<title>9</title>\n",
       "<path d=\"M236.3333,-21C236.3333,-21 226.6667,-21 226.6667,-21 223.8333,-21 221,-18.1667 221,-15.3333 221,-15.3333 221,-9.6667 221,-9.6667 221,-6.8333 223.8333,-4 226.6667,-4 226.6667,-4 236.3333,-4 236.3333,-4 239.1667,-4 242,-6.8333 242,-9.6667 242,-9.6667 242,-15.3333 242,-15.3333 242,-18.1667 239.1667,-21 236.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"225\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;9 -->\n",
       "<g class=\"edge\" id=\"edge3\">\n",
       "<title>0-&gt;9</title>\n",
       "<path d=\"M155.1679,-12.5C170.3001,-12.5 198.1052,-12.5 215.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"220.7448,-12.5 215.7449,-14.7501 218.2448,-12.5 215.7448,-12.5001 215.7448,-12.5001 215.7448,-12.5001 218.2448,-12.5 215.7448,-10.2501 220.7448,-12.5 220.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge2\">\n",
       "<title>1-&gt;0</title>\n",
       "<path d=\"M68.1679,-12.5C83.3001,-12.5 111.1052,-12.5 128.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"133.7448,-12.5 128.7449,-14.7501 131.2448,-12.5 128.7448,-12.5001 128.7448,-12.5001 128.7448,-12.5001 131.2448,-12.5 128.7448,-10.2501 133.7448,-12.5 133.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g class=\"node\" id=\"node4\">\n",
       "<title>2</title>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g class=\"node\" id=\"node5\">\n",
       "<title>3</title>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;2 -->\n",
       "<g class=\"edge\" id=\"edge9\">\n",
       "<title>3-&gt;2</title>\n",
       "<path d=\"M338.2416,-51.5C350.8112,-51.5 367.1985,-51.5 380.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"385.8365,-51.5 380.8365,-53.7501 383.3365,-51.5 380.8365,-51.5001 380.8365,-51.5001 380.8365,-51.5001 383.3365,-51.5 380.8364,-49.2501 385.8365,-51.5 385.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"359\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g class=\"node\" id=\"node6\">\n",
       "<title>4</title>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g class=\"edge\" id=\"edge8\">\n",
       "<title>4-&gt;3</title>\n",
       "<path d=\"M251.2416,-51.5C263.8112,-51.5 280.1985,-51.5 293.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"298.8365,-51.5 293.8365,-53.7501 296.3365,-51.5 293.8365,-51.5001 293.8365,-51.5001 293.8365,-51.5001 296.3365,-51.5 293.8364,-49.2501 298.8365,-51.5 298.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"272\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g class=\"node\" id=\"node7\">\n",
       "<title>5</title>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g class=\"edge\" id=\"edge7\">\n",
       "<title>5-&gt;4</title>\n",
       "<path d=\"M164.2416,-51.5C176.8112,-51.5 193.1985,-51.5 206.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"211.8365,-51.5 206.8365,-53.7501 209.3365,-51.5 206.8365,-51.5001 206.8365,-51.5001 206.8365,-51.5001 209.3365,-51.5 206.8364,-49.2501 211.8365,-51.5 211.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"185\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g class=\"node\" id=\"node8\">\n",
       "<title>6</title>\n",
       "<path d=\"M410.3333,-21C410.3333,-21 400.6667,-21 400.6667,-21 397.8333,-21 395,-18.1667 395,-15.3333 395,-15.3333 395,-9.6667 395,-9.6667 395,-6.8333 397.8333,-4 400.6667,-4 400.6667,-4 410.3333,-4 410.3333,-4 413.1667,-4 416,-6.8333 416,-9.6667 416,-9.6667 416,-15.3333 416,-15.3333 416,-18.1667 413.1667,-21 410.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<path d=\"M411.6667,-25C411.6667,-25 399.3333,-25 399.3333,-25 395.1667,-25 391,-20.8333 391,-16.6667 391,-16.6667 391,-8.3333 391,-8.3333 391,-4.1667 395.1667,0 399.3333,0 399.3333,0 411.6667,0 411.6667,0 415.8333,0 420,-4.1667 420,-8.3333 420,-8.3333 420,-16.6667 420,-16.6667 420,-20.8333 415.8333,-25 411.6667,-25\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"399\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g class=\"node\" id=\"node9\">\n",
       "<title>7</title>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;5 -->\n",
       "<g class=\"edge\" id=\"edge6\">\n",
       "<title>7-&gt;5</title>\n",
       "<path d=\"M77.2416,-51.5C89.8112,-51.5 106.1985,-51.5 119.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"124.8365,-51.5 119.8365,-53.7501 122.3365,-51.5 119.8365,-51.5001 119.8365,-51.5001 119.8365,-51.5001 122.3365,-51.5 119.8364,-49.2501 124.8365,-51.5 124.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"98\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g class=\"node\" id=\"node10\">\n",
       "<title>8</title>\n",
       "<path d=\"M323.3333,-21C323.3333,-21 313.6667,-21 313.6667,-21 310.8333,-21 308,-18.1667 308,-15.3333 308,-15.3333 308,-9.6667 308,-9.6667 308,-6.8333 310.8333,-4 313.6667,-4 313.6667,-4 323.3333,-4 323.3333,-4 326.1667,-4 329,-6.8333 329,-9.6667 329,-9.6667 329,-15.3333 329,-15.3333 329,-18.1667 326.1667,-21 323.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"312\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;6 -->\n",
       "<g class=\"edge\" id=\"edge5\">\n",
       "<title>8-&gt;6</title>\n",
       "<path d=\"M329.1679,-12.5C343.231,-12.5 368.2395,-12.5 385.7885,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"390.9749,-12.5 385.9749,-14.7501 388.4749,-12.5 385.9749,-12.5001 385.9749,-12.5001 385.9749,-12.5001 388.4749,-12.5 385.9749,-10.2501 390.9749,-12.5 390.9749,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;8 -->\n",
       "<g class=\"edge\" id=\"edge4\">\n",
       "<title>9-&gt;8</title>\n",
       "<path d=\"M242.1679,-12.5C257.3001,-12.5 285.1052,-12.5 302.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"307.7448,-12.5 302.7449,-14.7501 305.2448,-12.5 302.7448,-12.5001 302.7448,-12.5001 302.7448,-12.5001 305.2448,-12.5 302.7448,-10.2501 307.7448,-12.5 307.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "r = run(m, s)\n",
    "r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice. Does this run uses a state twice while reading in the first half of the string?\n",
    "\n",
    "Bill. Yes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "q1"
      ],
      "text/plain": [
       "Store(['q1'])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path = r.shortest_path()\n",
    "visited = set()\n",
    "for v in path[:p+1]:\n",
    "    if v[0] in visited:\n",
    "        q = v[0]\n",
    "        break\n",
    "    visited.add(v[0])\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice. What are the strings that it reads up to the first visit, between the first and second visits, and after the second visit?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[] ['0'] ['0', '1', '1']\n"
     ]
    }
   ],
   "source": [
    "indices = [i for i, v in enumerate(path) if v[0] == q]\n",
    "x = s[:indices[0]]\n",
    "y = s[indices[0]:indices[1]]\n",
    "z = s[indices[1]:]\n",
    "print(x, y, z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice. So, does your automaton accept this string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "s2 = x + y*2 + z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bill. Let's try it..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg height=\"76pt\" viewBox=\"0.00 0.00 520.00 75.50\" width=\"520pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g class=\"graph\" id=\"graph0\" transform=\"scale(1 1) rotate(0) translate(4 71.5)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" points=\"-4,4 -4,-71.5 516,-71.5 516,4 -4,4\" stroke=\"transparent\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\">\n",
       "<title>_START</title>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g class=\"node\" id=\"node8\">\n",
       "<title>6</title>\n",
       "<path d=\"M62.3333,-21C62.3333,-21 52.6667,-21 52.6667,-21 49.8333,-21 47,-18.1667 47,-15.3333 47,-15.3333 47,-9.6667 47,-9.6667 47,-6.8333 49.8333,-4 52.6667,-4 52.6667,-4 62.3333,-4 62.3333,-4 65.1667,-4 68,-6.8333 68,-9.6667 68,-9.6667 68,-15.3333 68,-15.3333 68,-18.1667 65.1667,-21 62.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"51\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;6 -->\n",
       "<g class=\"edge\" id=\"edge1\">\n",
       "<title>_START-&gt;6</title>\n",
       "<path d=\"M1.1401,-12.5C5.0617,-12.5 26.1734,-12.5 41.4077,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"46.7117,-12.5 41.7118,-14.7501 44.2117,-12.5 41.7117,-12.5001 41.7117,-12.5001 41.7117,-12.5001 44.2117,-12.5 41.7117,-10.2501 46.7117,-12.5 46.7117,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\">\n",
       "<title>0</title>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g class=\"node\" id=\"node3\">\n",
       "<title>1</title>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g class=\"node\" id=\"node5\">\n",
       "<title>3</title>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g class=\"edge\" id=\"edge9\">\n",
       "<title>1-&gt;3</title>\n",
       "<path d=\"M251.2416,-51.5C263.8112,-51.5 280.1985,-51.5 293.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"298.8365,-51.5 293.8365,-53.7501 296.3365,-51.5 293.8365,-51.5001 293.8365,-51.5001 293.8365,-51.5001 296.3365,-51.5 293.8364,-49.2501 298.8365,-51.5 298.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"272\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g class=\"node\" id=\"node4\">\n",
       "<title>2</title>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge11\">\n",
       "<title>2-&gt;0</title>\n",
       "<path d=\"M425.2416,-51.5C437.8112,-51.5 454.1985,-51.5 467.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"472.8365,-51.5 467.8365,-53.7501 470.3365,-51.5 467.8365,-51.5001 467.8365,-51.5001 467.8365,-51.5001 470.3365,-51.5 467.8364,-49.2501 472.8365,-51.5 472.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"446\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;2 -->\n",
       "<g class=\"edge\" id=\"edge10\">\n",
       "<title>3-&gt;2</title>\n",
       "<path d=\"M338.2416,-51.5C350.8112,-51.5 367.1985,-51.5 380.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"385.8365,-51.5 380.8365,-53.7501 383.3365,-51.5 380.8365,-51.5001 380.8365,-51.5001 380.8365,-51.5001 383.3365,-51.5 380.8364,-49.2501 385.8365,-51.5 385.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"359\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g class=\"node\" id=\"node6\">\n",
       "<title>4</title>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;1 -->\n",
       "<g class=\"edge\" id=\"edge8\">\n",
       "<title>4-&gt;1</title>\n",
       "<path d=\"M164.2416,-51.5C176.8112,-51.5 193.1985,-51.5 206.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"211.8365,-51.5 206.8365,-53.7501 209.3365,-51.5 206.8365,-51.5001 206.8365,-51.5001 206.8365,-51.5001 209.3365,-51.5 206.8364,-49.2501 211.8365,-51.5 211.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"185\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g class=\"node\" id=\"node7\">\n",
       "<title>5</title>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g class=\"edge\" id=\"edge7\">\n",
       "<title>5-&gt;4</title>\n",
       "<path d=\"M77.2416,-51.5C89.8112,-51.5 106.1985,-51.5 119.6505,-51.5\" fill=\"none\" stroke=\"#ffffff\"/>\n",
       "<polygon fill=\"#ffffff\" points=\"124.8365,-51.5 119.8365,-53.7501 122.3365,-51.5 119.8365,-51.5001 119.8365,-51.5001 119.8365,-51.5001 122.3365,-51.5 119.8364,-49.2501 124.8365,-51.5 124.8365,-51.5\" stroke=\"#ffffff\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"98\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g class=\"node\" id=\"node9\">\n",
       "<title>7</title>\n",
       "<path d=\"M149.3333,-21C149.3333,-21 139.6667,-21 139.6667,-21 136.8333,-21 134,-18.1667 134,-15.3333 134,-15.3333 134,-9.6667 134,-9.6667 134,-6.8333 136.8333,-4 139.6667,-4 139.6667,-4 149.3333,-4 149.3333,-4 152.1667,-4 155,-6.8333 155,-9.6667 155,-9.6667 155,-15.3333 155,-15.3333 155,-18.1667 152.1667,-21 149.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"138\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g class=\"edge\" id=\"edge2\">\n",
       "<title>6-&gt;7</title>\n",
       "<path d=\"M68.1679,-12.5C83.3001,-12.5 111.1052,-12.5 128.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"133.7448,-12.5 128.7449,-14.7501 131.2448,-12.5 128.7448,-12.5001 128.7448,-12.5001 128.7448,-12.5001 131.2448,-12.5 128.7448,-10.2501 133.7448,-12.5 133.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g class=\"node\" id=\"node12\">\n",
       "<title>10</title>\n",
       "<path d=\"M236.3333,-21C236.3333,-21 226.6667,-21 226.6667,-21 223.8333,-21 221,-18.1667 221,-15.3333 221,-15.3333 221,-9.6667 221,-9.6667 221,-6.8333 223.8333,-4 226.6667,-4 226.6667,-4 236.3333,-4 236.3333,-4 239.1667,-4 242,-6.8333 242,-9.6667 242,-9.6667 242,-15.3333 242,-15.3333 242,-18.1667 239.1667,-21 236.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"225\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;10 -->\n",
       "<g class=\"edge\" id=\"edge3\">\n",
       "<title>7-&gt;10</title>\n",
       "<path d=\"M155.1679,-12.5C170.3001,-12.5 198.1052,-12.5 215.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"220.7448,-12.5 215.7449,-14.7501 218.2448,-12.5 215.7448,-12.5001 215.7448,-12.5001 215.7448,-12.5001 218.2448,-12.5 215.7448,-10.2501 220.7448,-12.5 220.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g class=\"node\" id=\"node10\">\n",
       "<title>8</title>\n",
       "<path d=\"M497.3333,-21C497.3333,-21 487.6667,-21 487.6667,-21 484.8333,-21 482,-18.1667 482,-15.3333 482,-15.3333 482,-9.6667 482,-9.6667 482,-6.8333 484.8333,-4 487.6667,-4 487.6667,-4 497.3333,-4 497.3333,-4 500.1667,-4 503,-6.8333 503,-9.6667 503,-9.6667 503,-15.3333 503,-15.3333 503,-18.1667 500.1667,-21 497.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<path d=\"M498.6667,-25C498.6667,-25 486.3333,-25 486.3333,-25 482.1667,-25 478,-20.8333 478,-16.6667 478,-16.6667 478,-8.3333 478,-8.3333 478,-4.1667 482.1667,0 486.3333,0 486.3333,0 498.6667,0 498.6667,0 502.8333,0 507,-4.1667 507,-8.3333 507,-8.3333 507,-16.6667 507,-16.6667 507,-20.8333 502.8333,-25 498.6667,-25\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"486\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g class=\"node\" id=\"node11\">\n",
       "<title>9</title>\n",
       "<path d=\"M323.3333,-21C323.3333,-21 313.6667,-21 313.6667,-21 310.8333,-21 308,-18.1667 308,-15.3333 308,-15.3333 308,-9.6667 308,-9.6667 308,-6.8333 310.8333,-4 313.6667,-4 313.6667,-4 323.3333,-4 323.3333,-4 326.1667,-4 329,-6.8333 329,-9.6667 329,-9.6667 329,-15.3333 329,-15.3333 329,-18.1667 326.1667,-21 323.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"312\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g class=\"node\" id=\"node13\">\n",
       "<title>11</title>\n",
       "<path d=\"M410.3333,-21C410.3333,-21 400.6667,-21 400.6667,-21 397.8333,-21 395,-18.1667 395,-15.3333 395,-15.3333 395,-9.6667 395,-9.6667 395,-6.8333 397.8333,-4 400.6667,-4 400.6667,-4 410.3333,-4 410.3333,-4 413.1667,-4 416,-6.8333 416,-9.6667 416,-9.6667 416,-15.3333 416,-15.3333 416,-18.1667 413.1667,-21 410.3333,-21\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<text fill=\"#000000\" font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"399\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;11 -->\n",
       "<g class=\"edge\" id=\"edge5\">\n",
       "<title>9-&gt;11</title>\n",
       "<path d=\"M329.1679,-12.5C344.3001,-12.5 372.1052,-12.5 389.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"394.7448,-12.5 389.7449,-14.7501 392.2448,-12.5 389.7448,-12.5001 389.7448,-12.5001 389.7448,-12.5001 392.2448,-12.5 389.7448,-10.2501 394.7448,-12.5 394.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;9 -->\n",
       "<g class=\"edge\" id=\"edge4\">\n",
       "<title>10-&gt;9</title>\n",
       "<path d=\"M242.1679,-12.5C257.3001,-12.5 285.1052,-12.5 302.6535,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"307.7448,-12.5 302.7449,-14.7501 305.2448,-12.5 302.7448,-12.5001 302.7448,-12.5001 302.7448,-12.5001 305.2448,-12.5 302.7448,-10.2501 307.7448,-12.5 307.7448,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;8 -->\n",
       "<g class=\"edge\" id=\"edge6\">\n",
       "<title>11-&gt;8</title>\n",
       "<path d=\"M416.1679,-12.5C430.231,-12.5 455.2395,-12.5 472.7885,-12.5\" fill=\"none\" stroke=\"#000000\"/>\n",
       "<polygon fill=\"#000000\" points=\"477.9749,-12.5 472.9749,-14.7501 475.4749,-12.5 472.9749,-12.5001 472.9749,-12.5001 472.9749,-12.5001 475.4749,-12.5 472.9749,-10.2501 477.9749,-12.5 477.9749,-12.5\" stroke=\"#000000\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "run(m, s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bill. Doh!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The dialogue, general version\n",
    "\n",
    "In the dialogue above, Bill will lose no matter what automaton he produces. (You can try loading different automata to see what happens. If the automaton doesn't even accept $s$ in the first place, the dialogue will not make sense, but Bill still loses.) But it's not enough to try lots of automata; we need to show that Alice wins for _all_ automata. We now rewrite the dialogue with more generic responses from Bill to show that the argument works no matter what he says.\n",
    "\n",
    "Alice. The language $B = \\{\\texttt{0}^n \\texttt{1}^n \\mid n \\geq 0\\}$ is not regular.\n",
    "\n",
    "Bill. Yes it is! Here, I can show you an automaton that --\n",
    "\n",
    "Alice. No, I don't need to see it. Just count how many states it has.\n",
    "\n",
    "Bill. It has --\n",
    "\n",
    "Alice. No, I don't need to know. Just call it $p$.\n",
    "\n",
    "Bill. Okay.\n",
    "\n",
    "Alice. Does it accept the string $s = \\texttt{0}^p \\texttt{1}^p$?\n",
    "\n",
    "Bill. Yes.\n",
    "\n",
    "Alice. On reading the first $p$ symbols of $s$, your automaton goes through $(p+1)$ configurations (the starting configuration plus one for each symbol). Since your automaton has only $p$ states, it must be the case, by the pigeonhole principle, that it visits the same state twice.\n",
    "\n",
    "Bill. Yes.\n",
    "\n",
    "Alice. Could you find the strings that it reads up to the first visit, between the first and second visits, and after the second visit?\n",
    "\n",
    "Bill. Yes, they're --\n",
    "\n",
    "Alice. No, I don't need to know. Just call them $x$, $y$, and $z$, respectively.\n",
    "\n",
    "Bill. Okay.\n",
    "\n",
    "Alice. Does your automaton also accept $xy^2z$?\n",
    "\n",
    "Bill. Yes.\n",
    "\n",
    "Alice. But $y$ consists of only $\\texttt{0}$s, so $xy^2z$ has more $\\texttt{0}$s than $\\texttt{1}$s and does not belong to $B$.\n",
    "\n",
    "Bill. Doh!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The dialogue becomes a proof\n",
    "\n",
    "Notice that Bill has been reduced to agreeing with Alice. So we can just write him out of the dialogue.\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 finite automaton $M$ that generates $B$. Let $p$ be the number of states in $M$. By assumption, the string $s = \\texttt{0}^p \\texttt{1}^p$ is accepted by $M$. On reading the first $p$ symbols of $s$, $M$ goes through $(p+1)$ configurations (the starting configuration plus one for each symbol). Since $M$ has only $p$ states, it must be the case, by the pigeonhole principle, that it visits the same state twice. Let $x$ be the string read up to the first of those two visits, let $y$ be the string read between those two visits, and let $z$ be the rest of the string. Then $xy^2z$ must also be accepted by $M$. But $y$ must consist of only $\\texttt{0}$s. So $xy^2z$ has more $\\texttt{0}$s than $\\texttt{1}$s. It does not belong to $B$, yet is accepted by $M$, which is a contradiction."
   ]
  },
  {
   "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 $L$ is regular. Let $p$ be the pumping length given by the pumping lemma (line 2). Let $s = \\texttt{0}^p \\texttt{1}^p$ (line 3). Then the pumping lemma writes $s$ as $xyz$, where $|xy| \\leq p$ and $|y| > 0$ (line 4), which means that $y$ consists of only $\\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 wording is admittedly awkward. The phrases \"given by the pumping lemma\" and \"the pumping lemma writes\" (in the lines previously attributed to Bill) seem to come out of nowhere. 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 \\notin L$. 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": [
    "# Wednesday reading\n",
    "\n",
    "Re-read Section 1.4, paying closer attention this time to pages 80-82.\n",
    "\n",
    "# Thursday class\n",
    "\n",
    "## More practice with the pumping lemma\n",
    "\n",
    "**Question.** Prove that $L = \\{ 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.\n",
    "\n",
    "## Using closure properties\n",
    "\n",
    "Example 1.74 mentions an alternative proof strategy that involves the fact that regular languages are closed under intersection (footnote 3 of this chapter, a very important footnote!). This is an extremely common technique that lets you filter out strings that you don't want to deal with.\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, by intersecting with the language $\\mathtt{0}^\\ast\\mathtt{1}^\\ast$.\n",
    "\n",
    "Another commonly used property is closure under string homomorphisms (Exercise 1.66, 3rd ed. only). Any mapping $f : \\Sigma \\rightarrow \\Sigma^\\ast$ from symbols to strings can be extended to a mapping from strings to strings, called a string homomorphism, defined as follows:\n",
    "\n",
    "\\begin{align*}\n",
    "f(\\varepsilon) &= \\epsilon \\\\\n",
    "f(uv) &= f(u) f(v).\n",
    "\\end{align*}\n",
    "\n",
    "For example, if $\\Sigma = \\{\\mathtt{a}, \\mathtt{b}\\}$, and $f(\\mathtt{a}) = \\mathtt{a}, f(\\mathtt{b}) = \\varepsilon$, then $f$ extended to be a string homomorphism deletes all the $\\mathtt{b}$'s from a string. So this closure property lets you filter out symbols that you don't want to deal with. It also lets you conflate symbols that you don't need to distinguish.\n",
    "\n",
    "**Question.** Prove that if $L$ is regular, then $f(L)$ is regular.\n",
    "\n",
    "**Question.** Prove that $L = \\{w \\in \\{\\mathtt{a}, \\ldots, \\mathtt{z}\\}^\\ast \\mid \\text{$w$ contains an equal number of consonants and vowels}\\}$ is not regular."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}