13. The Pumping Lemma

In this one, we'll have a look at the pumping lemma, which is a nifty way to prove that a language does not belong to a particular class of languages. In particular, we'll give detailed examples for regular languages. It might seem boring, but I promise it does yield valuable insights in understanding what grammars can and cannot express.

Correction: It's probably incorrect that nested comments were forbidden in C because of regular expressions - I believe the original parser was hand-written. That being said, it's also harder to do by hand, and since C compilers later switched to lex (which uses regular expressions), that certainly didn't encourage switching to nested comments.