views:

709

answers:

4

The pumping lemma is a property of regular languages and context-free languages. But all the examples I've seen are things like:

L = {0n1n2n : n ≥ 0}

(which, incidentally, is not a context-free language).

But what I'm interested in is this: are there any examples of its use with any remotely real or useful languages? I haven't been able to find any. Is this one of those things or purely theoretical value with absolutely no practical application?

+7  A: 

L = {0n1n : n ≥ 0} being a context-free language.

Parenthesis matching in an expression can be considered to be of similar form i.e.

L = { (n )n : n ≥ 0}

Andriyev
Er... neither of these are what I call "real" languages. I know how it's applied to these artificial examples. What I want is at least one example of it being applied to a programming language or anything remotely "real world".
cletus
how is matching parentheses (or braces, quotes) not real world?
Otto Allmendinger
+1  A: 

One practical use is the fact that everyone can stop trying to construct a finite automaton to recognize the syntax of C# or Fortran.

Another practical use is the fact that everyone can stop trying to construct a pushdown automaton to recognize the semantics of C# or Fortran. (Even though in Fortran if you misspell a variable name you get a new variable for free, the new variable probably might not work with the operators that you coded when you intended to name one of your declared variables.)

Windows programmer
I'm not after a description of why it's useful but how it's been applied to a real language rather than sequences of abc or 012.
cletus
@cletus Designing a compiler happens outside the real world, in non real languages?
Justin Smith
+1  A: 

"Is this one of those things or purely theoretical value with absolutely no practical application?"

Hrm. What's a practical application? You wisely tagged your question "computer-science". So I suppose your question is meant to ask, "is it practical to computer science?

In which case, the answer is...

Of course it is! It is taught as one of the first ways of classifying different language complexity classes, beyond just "big-O(whateverthehell)". It shows that there are issues concerning computation beyond just runtime, in this case that some models simply cannot compute some functions.* It is a pretty low-ball introduction to formal proofs concerning automata theory.

A huge part of computer science that most computer science students (my peers) seem keen on avoiding is the Theory of Computation, a classification which pumping lemmas obviously fall under.

The hopefully obvious fact is that the theory of computation, like it or not, is foundational to computer science. To not grasp the idea of different complexity classes (big-O by itself really doesn't cut it) will not spell the death of the computer scientist, but it will hide a considerable portion of the field from his or her view.

*Yes, usually the halting problem is shown as the first, but they never get it the first time around.

As for perhaps the more cynical interpretation of your question, in which you mean "does any piece of software really use this?", my answer is of course not. It is part of the foundation of computation, not its applications. This is not to sound dismissive of its applications, not at all. Both are of equal, noble worth.

Agor
That's a lovely speech and all but it doesn't answer the question: I"m after real world examples of its use.
cletus
Maybe you missed the forest for the trees. **Education**. Or perhaps you'd better clarify by what you mean by "real world"? :P
Agor
+1  A: 

this python program is valid:

print ((((((((((((((((((((((((1))))))))))))))))))))))))

as well as all other equivalent statements with an equal amount of ( on the left and ) on the right side.

You cannot build a regular expression to verify that, thus you have to use a parser.

It is not at all theoretical. It is the reason why you cannot use regex to parse HTML.

Otto Allmendinger