Wednesday, August 21, 2013 [Tweets] [Favorites]

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

Stay up-to-date by subscribing to the Comments RSS Feed for this post.

Leave a Comment