Question

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?

Answer 1

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.

Answer 2

Let L_n 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.

Answer 3

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.

Answer 4

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.