{
"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": [
""
],
"text/plain": [
""
]
},
"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": [
""
],
"text/plain": [
""
]
},
"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": [
""
],
"text/plain": [
""
]
},
"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
}