## Regular languages and the pumping lemma

In certain dark corners of computer science and group theory, one often wants to prove that a language is not a regular language (ie a language accepted by a finite state automaton).

The only general technique I know for doing this is the so-called "pumping lemma", which says that if L is a regular language, then there exists some n>0 with the following property. If w is a word in L of length at least n, then we can write w=xyz (here x, y, and z are subwords) such that y is nontrivial and xy^{k}z is an element of L for all k>0.

This lemma basically reflects the trivial fact that in any directed graph, there is some n such that any path of length at least n contains a loop.

Question : are there any other general techniques for proving that a language is not regular?

-

For necessary and sufficient conditions for a language to be regular (sometimes useful in proving nonregularity when simpler tricks like the pumping lemma fail) see the Myhill–Nerode theorem.

-

Let Ln be the number of words in L of length n. If sum L_n x^n is not a rational function, then L can't be regular. See the proof in the comments.

-
Flajolet and Sedgewick's text "Analytic Combinatorics" is available online here: algo.inria.fr/flajolet/Publications/books.html The proof can be done using both definitions of a regular language: if you define a regular language in terms of a regular grammar, this is equivalent to specifying the above generating function using sums, products, and the "Kleene star" 1/(1-x). If you define a regular language in terms of recognizability by a state machine G, then you can extract the generating function by considering 1/(I-At) where A is the adjacency matrix. – Qiaochu Yuan Oct 20 2009 at 4:47
Simply awesome. Thanks for making me aware of this. – Andrew Critch Oct 20 2009 at 4:51
I'm curious about the "language is unambiguous" part. I would have thought that unambiguous-ness was a property of a grammar, not a language. What does "unambiguous" mean, and how do you prove it for the language of Dyck words? – Reid Barton Oct 20 2009 at 4:53
Hmm. According to Google there is a notion of "inherently ambiguous" language, which is a language with the property that every grammar describing it is ambiguous. But the search results I'm getting don't agree on whether there exist inherently ambiguous regular languages. – Qiaochu Yuan Oct 20 2009 at 5:04

Another good way to prove language L non-regular is to find a regular language A such that L∩A is non-regular.

For example, one can take A = a*b*, and prove that L∩A = {a^nb^n : n≥0}.

This method works because the intersection of two regular languages is always regular.

-

Some variants of the pumping lemma are complete for determining whether a language L is regular. For example, consider this two player game:

Player 1 picks a positive integer k. Player 2 picks a string w of length k. Player 1 picks a string partition w=abc, with b non-empty. Player 2 picks z so exactly one of {wz, acz} is in L. The last player to make a valid move wins.

Then L is regular iff Player 1 has a winning strategy. This comes down to Myhill-Nerode, as mentioned earlier. For a similar example, see Jaffe.

-