Regular languages and the pumping lemma 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?
 A: 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.
A: The usual pumping lemma gives only a necessary condition for a language to be regular,
but there are more powerful versions giving necessary and sufficient conditions, using "block pumping properties".
A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, SIAM
J. Comput. 10 (1981), 536-541.
S. Varricchio, A Pumping Condition for Regular Sets, SIAM J. Comput. 26 (1997), 764–771.
A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages (Monographs in Theoretical Computer Science. An EATCS Series), Springer 1999.
ISBN: 978-3-540-63771-4 (Print) 978-3-642-59849-4 (Online)
A: The following lemma, which I saw in some old book, can handle most textbook examples of pumping lemma usage and is usually much easier to apply when it does apply.  Let $L$ be a language, and suppose there are strings $\alpha_1,\alpha_2,\ldots $ and $\beta_1,\beta_2,\ldots$ with the property that $\alpha_i\beta_j\in L$ iff $i=j$.  Then $L$ is not regular (easy proof using a DFA).
Note that the $\alpha$s and $\beta$s are just strings, they don't need to be in $L$ and usually aren't.
Examples:


*

*$\alpha_k:=a^k$ and $\beta_k:=b^k$ shows $\lbrace a^kb^k : k\ge 0\rbrace$ is not regular. 

*$\alpha_k:=a^k$ and $\beta_k:=ba^k$ shows the set of palindromes is not regular.

*$\alpha_k:=ba^k$ and $\beta_k:=ba^k$ shows $\lbrace ww : w\in\Sigma^*\rbrace$ is not regular. 

A: 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.
A: 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.
A: 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.
