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?