5
$\begingroup$

The pumping lemmata (for regular languages and for context free languages) are used to prove languages non-regular/non-context free by contradiction. But such proofs are often horribly botched by students. Any insights on how to explain how to use them?

For reference, the pumping lemma for regular language (the context free one is similar): If $L$ is a regular language, then there is a constant $N \in \mathbb{N}$ such that all strings $\sigma \in L$ that are longer than $N$ ca be written $\sigma = \alpha \beta \gamma$, where the length of $\alpha \beta$ is at most $N$, $\beta$ isn't empty, and for all $k \in \mathbb{N}_0$ you have $\alpha \beta^k \gamma \in L$.

Typical mistakes are, roughly in decreasing order of occurrence:

  • Picking some nice $N$
  • Selecting a particular split
  • Not making sure the selected $\sigma$ is long enough

Other mistakes, not fatal ones, are:

  • Making sure $\sigma$ is (almost) exactly of length $N$
  • Selecting awkward values of $k$ to derive a contradiction
$\endgroup$
  • $\begingroup$ I've misplaced my copy of Sipser's book, but my sense is (was) he explains it pretty well. As far as instructive examples, I recall starting with something like: $L = \{0^n 1^n | n\geq 0\}$ is not regular. (Proof: Given $N$ from the pumping lemma, let $\sigma = 0^N 1^N$. Then it must be that $\alpha = 0^a, \beta = 0^b, \gamma = 0^{N-a-b} 1^N$ for $a, b$ such that $a+b \leq N$ and $b > 0$. So the string $\alpha \beta^2 \gamma = 0^{N+b} 1^N \in L$; but $b >0$, so $\alpha \beta^2 \gamma \not\in L$. Contradiction. Therefore, $L$ is not regular. QED.) $\endgroup$ – Benjamin Dickman Jun 15 '14 at 20:34
  • $\begingroup$ @BenjaminDickman I'll take a second look at Sipser's book. I just remember the one in Aho, Hopcroft, Ullman $\endgroup$ – vonbrand Jun 15 '14 at 23:20
  • $\begingroup$ Perhaps I should expand this question a bit. The pumping lemmata are perhaps the first results that require more complex reasoning to apply (not just "check the hypothesis, result follows"), and maybe the snag is there? $\endgroup$ – vonbrand Jun 16 '14 at 11:51
2
$\begingroup$

In my opinion the main issue is that the pumping lemma is often presented as a black box, many students ignorant of the basic idea behind it. Because of this I prefer to use the "pumping lemma" phrase as a concise way of saying all the following:

  • A finite automaton has finite number of states, so for any (sub)word of length greater than $|A|$ some state has to repeat in the automaton run.
  • If some state happens more than once in a single word, then there exists a non-empty substring $\beta$ that leads from that state to itself.
  • Independent of how many times we repeat $\beta$, the rest of the automaton run stays unchanged.
  • In particular, the word's acceptance doesn't change.

Each bullet above is intuitive and doesn't pose any problems, even for weaker students. I've never seen anyone to err while having such an operational intuition in mind (I'm not saying that it doesn't happen, only that it is rarer). Yet, there are people who don't understand it this way despite having seen the proof.

This is why I would prefer to stop presenting it as a lemma we use to prove non-regularity (and make some students disregard the proof), but rather each time prove non-regularity from scratch and then call such approach in general a proof "via pumping lemma".

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ The proof of the pumping lemmata is shown in detail, with quite a bit of explanation. And one of the points I stress is that the whole idea of theorem/corollary/lemma/proposition is to use them to simplify/shorten your work. $\endgroup$ – vonbrand Jun 16 '14 at 11:28
  • $\begingroup$ @vonbrand Good for you. How do you explain then that some miss the understanding? There are some theorems that thinking in terms of its proof would be inconvenient. However, the pumping lemma isn't one of them. $\endgroup$ – dtldarek Jun 16 '14 at 11:35
  • $\begingroup$ Yes, that is more or less why I'm asking $\endgroup$ – vonbrand Jun 16 '14 at 11:37
  • $\begingroup$ @vonbrand: Students don't think of proofs as explanations of why something is true (even though that's what they are). Students think of proofs as "OK, now the prof. is going to draw on the board for 20 minutes, which we are going to ignore because it isn't on the test, and from then on until the end of time, we can just assume the lemma is true without having to derive it." The problem is that without the proof, the lemma comes across as really abstract and hard to understand, so students following that strategy have great difficulty with it. $\endgroup$ – Kevin Mar 17 '18 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.