Wednesday, August 21, 2013

The Pumping Lemma, The Pigeonhole Principle, and Differentiating Languages

Robin Houston (via @CompSciFact):

I hate the Pumping Lemma for regular languages. It’s a complicated way to express an idea that is fundamentally very simple, and it isn’t even a very good way to prove that a language is not regular.


It’s easy enough to see that any derivative of a regular language is again regular: taking a derivative just corresponds to changing the start state in a deterministic automaton. By the same argument, any regular language has only a finite number of different derivatives.

Comments RSS · Twitter

Leave a Comment