<story><title>I hate the Pumping Lemma</title><url>http://bosker.wordpress.com/2013/08/18/i-hate-the-pumping-lemma/</url></story><parent_chain></parent_chain><comment><author>xyzzyz</author><text>&lt;i&gt;The real insult is that the actual underlying idea, and the proof, is shockingly simple. It is essentially the pigeonhole principle: the principle that if you put more than n pigeons into n holes then there must be a hole with more than one pigeon in. Take the regular language L, and express it as a deterministic finite automaton with p states. Any string in L determines a path through the automaton; so any string with p or more characters must visit the same state twice, forming a loop. This looped part can be repeated any arbitrary number of times to produce other strings in L.&lt;/i&gt;&lt;p&gt;Yeah, that&amp;#x27;s how it is usually introduced to students. First you introduce them to finite state automatons, then you show them a cool trick of extending the words by walking in circles on the automaton&amp;#x27;s state graph, and only then you mention that this is basically a pumping lemma. After everyone understood the point of the pumping lemma, you write it down formally using five quantifiers, so that student can write it down concisely, as the idea is already understood at that point.&lt;p&gt;I agree that the formal statement of the pumping lemma can be very uninspiring, but it only hints to two important facts. First, it&amp;#x27;s very important to have a good teacher, who is able to introduce ideas in a way and order they work for you. Second is that in math, it&amp;#x27;s the proofs and ideas that are important, not theorem statements.</text></comment>
<story><title>I hate the Pumping Lemma</title><url>http://bosker.wordpress.com/2013/08/18/i-hate-the-pumping-lemma/</url></story><parent_chain></parent_chain><comment><author>a8i</author><text>Ironically, this post&amp;#x27;s explanation caused me understand the pumping lemma for the first time after years of letting my eyes just slide over any time I read across a mention.&lt;p&gt;(It nerdsniped me by claiming it was difficult.)</text></comment>