Let's say that I want to prove that a language is not regular.


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?



Regular languages and the pumping lemma
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](http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem).


