notes/week04/week04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 4: 2017/02/06-10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "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 simple. 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": {
    "collapsed": false
   },
   "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=\"white\" points=\"-4,4 -4,-63 140,-63 140,4 -4,4\" stroke=\"none\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\"><title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\"><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.66667 38,-9.66667 38,-6.83333 40.8333,-4 43.6667,-4 43.6667,-4 53.3333,-4 53.3333,-4 56.1667,-4 59,-6.83333 59,-9.66667 59,-9.66667 59,-15.3333 59,-15.3333 59,-18.1667 56.1667,-21 53.3333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text 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\"><title>_START-&gt;0</title>\n",
       "<path d=\"M1.13339,-12.5C2.79277,-12.5 19.5956,-12.5 32.5011,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"37.7379,-12.5 32.738,-14.7501 35.2379,-12.5 32.7379,-12.5001 32.7379,-12.5001 32.7379,-12.5001 35.2379,-12.5 32.7379,-10.2501 37.7379,-12.5 37.7379,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge2\"><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=\"black\"/>\n",
       "<polygon fill=\"black\" 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=\"black\"/>\n",
       "<text 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\"><title>1</title>\n",
       "<path d=\"M126.333,-21C126.333,-21 116.667,-21 116.667,-21 113.833,-21 111,-18.1667 111,-15.3333 111,-15.3333 111,-9.66667 111,-9.66667 111,-6.83333 113.833,-4 116.667,-4 116.667,-4 126.333,-4 126.333,-4 129.167,-4 132,-6.83333 132,-9.66667 132,-9.66667 132,-15.3333 132,-15.3333 132,-18.1667 129.167,-21 126.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<path d=\"M127.667,-25C127.667,-25 115.333,-25 115.333,-25 111.167,-25 107,-20.8333 107,-16.6667 107,-16.6667 107,-8.33333 107,-8.33333 107,-4.16667 111.167,-0 115.333,-0 115.333,-0 127.667,-0 127.667,-0 131.833,-0 136,-4.16667 136,-8.33333 136,-8.33333 136,-16.6667 136,-16.6667 136,-20.8333 131.833,-25 127.667,-25\" fill=\"none\" stroke=\"black\"/>\n",
       "<text 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\"><title>0-&gt;1</title>\n",
       "<path d=\"M59.0754,-12.5C69.9689,-12.5 88.0236,-12.5 101.747,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"106.956,-12.5 101.956,-14.7501 104.456,-12.5 101.956,-12.5001 101.956,-12.5001 101.956,-12.5001 104.456,-12.5 101.956,-10.2501 106.956,-12.5 106.956,-12.5\" stroke=\"black\"/>\n",
       "<text 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\"><title>1-&gt;1</title>\n",
       "<path d=\"M115.142,-25.0318C113.072,-34.0334 115.191,-43 121.5,-43 126.626,-43 128.986,-37.0807 128.58,-30.0327\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"127.858,-25.0318 130.8,-29.6587 128.215,-27.5061 128.573,-29.9804 128.573,-29.9804 128.573,-29.9804 128.215,-27.5061 126.346,-30.3022 127.858,-25.0318 127.858,-25.0318\" stroke=\"black\"/>\n",
       "<text 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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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=\"white\" points=\"-4,4 -4,-71.5 429,-71.5 429,4 -4,4\" stroke=\"none\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\"><title>_START</title>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\"><title>0</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.66667 47,-9.66667 47,-6.83333 49.8333,-4 52.6667,-4 52.6667,-4 62.3333,-4 62.3333,-4 65.1667,-4 68,-6.83333 68,-9.66667 68,-9.66667 68,-15.3333 68,-15.3333 68,-18.1667 65.1667,-21 62.3333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"51\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- _START&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge1\"><title>_START-&gt;0</title>\n",
       "<path d=\"M1.15921,-12.5C3.26572,-12.5 25.8189,-12.5 41.4749,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"46.8802,-12.5 41.8802,-14.7501 44.3802,-12.5 41.8802,-12.5001 41.8802,-12.5001 41.8802,-12.5001 44.3802,-12.5 41.8801,-10.2501 46.8802,-12.5 46.8802,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g class=\"node\" id=\"node3\"><title>1</title>\n",
       "<path d=\"M149.333,-21C149.333,-21 139.667,-21 139.667,-21 136.833,-21 134,-18.1667 134,-15.3333 134,-15.3333 134,-9.66667 134,-9.66667 134,-6.83333 136.833,-4 139.667,-4 139.667,-4 149.333,-4 149.333,-4 152.167,-4 155,-6.83333 155,-9.66667 155,-9.66667 155,-15.3333 155,-15.3333 155,-18.1667 152.167,-21 149.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"138\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g class=\"edge\" id=\"edge2\"><title>0-&gt;1</title>\n",
       "<path d=\"M68.2506,-12.5C82.9815,-12.5 111.032,-12.5 128.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"133.863,-12.5 128.863,-14.7501 131.363,-12.5 128.863,-12.5001 128.863,-12.5001 128.863,-12.5001 131.363,-12.5 128.863,-10.2501 133.863,-12.5 133.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g class=\"node\" id=\"node4\"><title>2</title>\n",
       "<path d=\"M236.333,-21C236.333,-21 226.667,-21 226.667,-21 223.833,-21 221,-18.1667 221,-15.3333 221,-15.3333 221,-9.66667 221,-9.66667 221,-6.83333 223.833,-4 226.667,-4 226.667,-4 236.333,-4 236.333,-4 239.167,-4 242,-6.83333 242,-9.66667 242,-9.66667 242,-15.3333 242,-15.3333 242,-18.1667 239.167,-21 236.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"225\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g class=\"edge\" id=\"edge9\"><title>1-&gt;2</title>\n",
       "<path d=\"M155.251,-12.5C169.982,-12.5 198.032,-12.5 215.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"220.863,-12.5 215.863,-14.7501 218.363,-12.5 215.863,-12.5001 215.863,-12.5001 215.863,-12.5001 218.363,-12.5 215.863,-10.2501 220.863,-12.5 220.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g class=\"node\" id=\"node5\"><title>3</title>\n",
       "<path d=\"M323.333,-21C323.333,-21 313.667,-21 313.667,-21 310.833,-21 308,-18.1667 308,-15.3333 308,-15.3333 308,-9.66667 308,-9.66667 308,-6.83333 310.833,-4 313.667,-4 313.667,-4 323.333,-4 323.333,-4 326.167,-4 329,-6.83333 329,-9.66667 329,-9.66667 329,-15.3333 329,-15.3333 329,-18.1667 326.167,-21 323.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"312\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g class=\"edge\" id=\"edge8\"><title>2-&gt;3</title>\n",
       "<path d=\"M242.251,-12.5C256.982,-12.5 285.032,-12.5 302.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"307.863,-12.5 302.863,-14.7501 305.363,-12.5 302.863,-12.5001 302.863,-12.5001 302.863,-12.5001 305.363,-12.5 302.863,-10.2501 307.863,-12.5 307.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g class=\"node\" id=\"node6\"><title>4</title>\n",
       "<path d=\"M410.333,-21C410.333,-21 400.667,-21 400.667,-21 397.833,-21 395,-18.1667 395,-15.3333 395,-15.3333 395,-9.66667 395,-9.66667 395,-6.83333 397.833,-4 400.667,-4 400.667,-4 410.333,-4 410.333,-4 413.167,-4 416,-6.83333 416,-9.66667 416,-9.66667 416,-15.3333 416,-15.3333 416,-18.1667 413.167,-21 410.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<path d=\"M411.667,-25C411.667,-25 399.333,-25 399.333,-25 395.167,-25 391,-20.8333 391,-16.6667 391,-16.6667 391,-8.33333 391,-8.33333 391,-4.16667 395.167,-0 399.333,-0 399.333,-0 411.667,-0 411.667,-0 415.833,-0 420,-4.16667 420,-8.33333 420,-8.33333 420,-16.6667 420,-16.6667 420,-20.8333 415.833,-25 411.667,-25\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"399\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g class=\"edge\" id=\"edge7\"><title>3-&gt;4</title>\n",
       "<path d=\"M329.251,-12.5C343.003,-12.5 368.364,-12.5 385.815,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"390.955,-12.5 385.955,-14.7501 388.455,-12.5 385.955,-12.5001 385.955,-12.5001 385.955,-12.5001 388.455,-12.5 385.955,-10.2501 390.955,-12.5 390.955,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g class=\"node\" id=\"node7\"><title>5</title>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g class=\"node\" id=\"node8\"><title>6</title>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g class=\"edge\" id=\"edge6\"><title>5-&gt;6</title>\n",
       "<path d=\"M77.3643,-51.5C89.8859,-51.5 106.421,-51.5 119.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"124.981,-51.5 119.981,-53.7501 122.481,-51.5 119.981,-51.5001 119.981,-51.5001 119.981,-51.5001 122.481,-51.5 119.981,-49.2501 124.981,-51.5 124.981,-51.5\" stroke=\"white\"/>\n",
       "<text 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\"><title>7</title>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g class=\"edge\" id=\"edge5\"><title>6-&gt;7</title>\n",
       "<path d=\"M164.364,-51.5C176.886,-51.5 193.421,-51.5 206.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"211.981,-51.5 206.981,-53.7501 209.481,-51.5 206.981,-51.5001 206.981,-51.5001 206.981,-51.5001 209.481,-51.5 206.981,-49.2501 211.981,-51.5 211.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"185\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g class=\"node\" id=\"node10\"><title>8</title>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g class=\"edge\" id=\"edge4\"><title>7-&gt;8</title>\n",
       "<path d=\"M251.364,-51.5C263.886,-51.5 280.421,-51.5 293.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"298.981,-51.5 293.981,-53.7501 296.481,-51.5 293.981,-51.5001 293.981,-51.5001 293.981,-51.5001 296.481,-51.5 293.981,-49.2501 298.981,-51.5 298.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"272\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g class=\"node\" id=\"node11\"><title>9</title>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g class=\"edge\" id=\"edge3\"><title>8-&gt;9</title>\n",
       "<path d=\"M338.364,-51.5C350.886,-51.5 367.421,-51.5 380.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"385.981,-51.5 380.981,-53.7501 383.481,-51.5 380.981,-51.5001 380.981,-51.5001 380.981,-51.5001 383.481,-51.5 380.981,-49.2501 385.981,-51.5 385.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"359\" y=\"-57.3\">1</text>\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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s2 = x + y*2 + z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bill. Let's try it..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "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=\"white\" points=\"-4,4 -4,-71.5 516,-71.5 516,4 -4,4\" stroke=\"none\"/>\n",
       "<!-- _START -->\n",
       "<g class=\"node\" id=\"node1\"><title>_START</title>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g class=\"node\" id=\"node3\"><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.66667 47,-9.66667 47,-6.83333 49.8333,-4 52.6667,-4 52.6667,-4 62.3333,-4 62.3333,-4 65.1667,-4 68,-6.83333 68,-9.66667 68,-9.66667 68,-15.3333 68,-15.3333 68,-18.1667 65.1667,-21 62.3333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text 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\"><title>_START-&gt;1</title>\n",
       "<path d=\"M1.15921,-12.5C3.26572,-12.5 25.8189,-12.5 41.4749,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"46.8802,-12.5 41.8802,-14.7501 44.3802,-12.5 41.8802,-12.5001 41.8802,-12.5001 41.8802,-12.5001 44.3802,-12.5 41.8801,-10.2501 46.8802,-12.5 46.8802,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g class=\"node\" id=\"node2\"><title>0</title>\n",
       "<path d=\"M149.333,-21C149.333,-21 139.667,-21 139.667,-21 136.833,-21 134,-18.1667 134,-15.3333 134,-15.3333 134,-9.66667 134,-9.66667 134,-6.83333 136.833,-4 139.667,-4 139.667,-4 149.333,-4 149.333,-4 152.167,-4 155,-6.83333 155,-9.66667 155,-9.66667 155,-15.3333 155,-15.3333 155,-18.1667 152.167,-21 149.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"138\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g class=\"node\" id=\"node5\"><title>3</title>\n",
       "<path d=\"M236.333,-21C236.333,-21 226.667,-21 226.667,-21 223.833,-21 221,-18.1667 221,-15.3333 221,-15.3333 221,-9.66667 221,-9.66667 221,-6.83333 223.833,-4 226.667,-4 226.667,-4 236.333,-4 236.333,-4 239.167,-4 242,-6.83333 242,-9.66667 242,-9.66667 242,-15.3333 242,-15.3333 242,-18.1667 239.167,-21 236.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"225\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;3 -->\n",
       "<g class=\"edge\" id=\"edge2\"><title>0-&gt;3</title>\n",
       "<path d=\"M155.251,-12.5C169.982,-12.5 198.032,-12.5 215.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"220.863,-12.5 215.863,-14.7501 218.363,-12.5 215.863,-12.5001 215.863,-12.5001 215.863,-12.5001 218.363,-12.5 215.863,-10.2501 220.863,-12.5 220.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g class=\"edge\" id=\"edge9\"><title>1-&gt;0</title>\n",
       "<path d=\"M68.2506,-12.5C82.9815,-12.5 111.032,-12.5 128.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"133.863,-12.5 128.863,-14.7501 131.363,-12.5 128.863,-12.5001 128.863,-12.5001 128.863,-12.5001 131.363,-12.5 128.863,-10.2501 133.863,-12.5 133.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g class=\"node\" id=\"node4\"><title>2</title>\n",
       "<path d=\"M410.333,-21C410.333,-21 400.667,-21 400.667,-21 397.833,-21 395,-18.1667 395,-15.3333 395,-15.3333 395,-9.66667 395,-9.66667 395,-6.83333 397.833,-4 400.667,-4 400.667,-4 410.333,-4 410.333,-4 413.167,-4 416,-6.83333 416,-9.66667 416,-9.66667 416,-15.3333 416,-15.3333 416,-18.1667 413.167,-21 410.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"399\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g class=\"node\" id=\"node7\"><title>5</title>\n",
       "<path d=\"M497.333,-21C497.333,-21 487.667,-21 487.667,-21 484.833,-21 482,-18.1667 482,-15.3333 482,-15.3333 482,-9.66667 482,-9.66667 482,-6.83333 484.833,-4 487.667,-4 487.667,-4 497.333,-4 497.333,-4 500.167,-4 503,-6.83333 503,-9.66667 503,-9.66667 503,-15.3333 503,-15.3333 503,-18.1667 500.167,-21 497.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<path d=\"M498.667,-25C498.667,-25 486.333,-25 486.333,-25 482.167,-25 478,-20.8333 478,-16.6667 478,-16.6667 478,-8.33333 478,-8.33333 478,-4.16667 482.167,-0 486.333,-0 486.333,-0 498.667,-0 498.667,-0 502.833,-0 507,-4.16667 507,-8.33333 507,-8.33333 507,-16.6667 507,-16.6667 507,-20.8333 502.833,-25 498.667,-25\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"486\" y=\"-10\">q2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g class=\"edge\" id=\"edge7\"><title>2-&gt;5</title>\n",
       "<path d=\"M416.251,-12.5C430.003,-12.5 455.364,-12.5 472.815,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"477.955,-12.5 472.955,-14.7501 475.455,-12.5 472.955,-12.5001 472.955,-12.5001 472.955,-12.5001 475.455,-12.5 472.955,-10.2501 477.955,-12.5 477.955,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g class=\"node\" id=\"node6\"><title>4</title>\n",
       "<path d=\"M323.333,-21C323.333,-21 313.667,-21 313.667,-21 310.833,-21 308,-18.1667 308,-15.3333 308,-15.3333 308,-9.66667 308,-9.66667 308,-6.83333 310.833,-4 313.667,-4 313.667,-4 323.333,-4 323.333,-4 326.167,-4 329,-6.83333 329,-9.66667 329,-9.66667 329,-15.3333 329,-15.3333 329,-18.1667 326.167,-21 323.333,-21\" fill=\"none\" stroke=\"black\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"10.00\" text-anchor=\"start\" x=\"312\" y=\"-10\">q1</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g class=\"edge\" id=\"edge11\"><title>3-&gt;4</title>\n",
       "<path d=\"M242.251,-12.5C256.982,-12.5 285.032,-12.5 302.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"307.863,-12.5 302.863,-14.7501 305.363,-12.5 302.863,-12.5001 302.863,-12.5001 302.863,-12.5001 305.363,-12.5 302.863,-10.2501 307.863,-12.5 307.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;2 -->\n",
       "<g class=\"edge\" id=\"edge10\"><title>4-&gt;2</title>\n",
       "<path d=\"M329.251,-12.5C343.982,-12.5 372.032,-12.5 389.412,-12.5\" fill=\"none\" stroke=\"black\"/>\n",
       "<polygon fill=\"black\" points=\"394.863,-12.5 389.863,-14.7501 392.363,-12.5 389.863,-12.5001 389.863,-12.5001 389.863,-12.5001 392.363,-12.5 389.863,-10.2501 394.863,-12.5 394.863,-12.5\" stroke=\"black\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g class=\"node\" id=\"node8\"><title>6</title>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g class=\"node\" id=\"node9\"><title>7</title>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g class=\"edge\" id=\"edge6\"><title>6-&gt;7</title>\n",
       "<path d=\"M77.3643,-51.5C89.8859,-51.5 106.421,-51.5 119.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"124.981,-51.5 119.981,-53.7501 122.481,-51.5 119.981,-51.5001 119.981,-51.5001 119.981,-51.5001 122.481,-51.5 119.981,-49.2501 124.981,-51.5 124.981,-51.5\" stroke=\"white\"/>\n",
       "<text 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\"><title>8</title>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g class=\"edge\" id=\"edge5\"><title>7-&gt;8</title>\n",
       "<path d=\"M164.364,-51.5C176.886,-51.5 193.421,-51.5 206.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"211.981,-51.5 206.981,-53.7501 209.481,-51.5 206.981,-51.5001 206.981,-51.5001 206.981,-51.5001 209.481,-51.5 206.981,-49.2501 211.981,-51.5 211.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"185\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g class=\"node\" id=\"node11\"><title>9</title>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g class=\"edge\" id=\"edge4\"><title>8-&gt;9</title>\n",
       "<path d=\"M251.364,-51.5C263.886,-51.5 280.421,-51.5 293.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"298.981,-51.5 293.981,-53.7501 296.481,-51.5 293.981,-51.5001 293.981,-51.5001 293.981,-51.5001 296.481,-51.5 293.981,-49.2501 298.981,-51.5 298.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"272\" y=\"-57.3\">0</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g class=\"node\" id=\"node12\"><title>10</title>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g class=\"edge\" id=\"edge3\"><title>9-&gt;10</title>\n",
       "<path d=\"M338.364,-51.5C350.886,-51.5 367.421,-51.5 380.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"385.981,-51.5 380.981,-53.7501 383.481,-51.5 380.981,-51.5001 380.981,-51.5001 380.981,-51.5001 383.481,-51.5 380.981,-49.2501 385.981,-51.5 385.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"359\" y=\"-57.3\">1</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g class=\"node\" id=\"node13\"><title>11</title>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g class=\"edge\" id=\"edge8\"><title>10-&gt;11</title>\n",
       "<path d=\"M425.364,-51.5C437.886,-51.5 454.421,-51.5 467.825,-51.5\" fill=\"none\" stroke=\"white\"/>\n",
       "<polygon fill=\"white\" points=\"472.981,-51.5 467.981,-53.7501 470.481,-51.5 467.981,-51.5001 467.981,-51.5001 467.981,-51.5001 470.481,-51.5 467.981,-49.2501 472.981,-51.5 472.981,-51.5\" stroke=\"white\"/>\n",
       "<text font-family=\"Courier,monospace\" font-size=\"9.00\" text-anchor=\"start\" x=\"446\" y=\"-57.3\">1</text>\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 variables in place of Bill's responses 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 tell me how many states it has.\n",
    "\n",
    "Bill. It has $p$ states.\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. What are the strings that it reads up to the first visit, between the first and second visits, and after the second visit?\n",
    "\n",
    "Bill. $x$, $y$, and $z$.\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 uttering variables and 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\" (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",
    "Course Project 1 is due tonight.\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."
   ]
  }
 ],
 "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}