Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

6 Answers 6

up vote 12 down vote accepted

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.

share|improve this answer
1  
I'd say more (and do so when I teach the material). There's really no point in learning anything but Myhill-Nerode which is both more general, and natural (though I hate the name for the usual reason that it says nothing about the result). –  Michael Albert Aug 14 '13 at 4:15
add comment

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.

share|improve this answer
2  
THAT. IS. AWESOME. Where can I read more about this? –  Andrew Critch Oct 20 '09 at 4:29
3  
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 '09 at 4:47
    
Simply awesome. Thanks for making me aware of this. –  Andrew Critch Oct 20 '09 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 '09 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 '09 at 5:04
show 6 more comments

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.

share|improve this answer
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
add comment

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:

  1. $\alpha_k:=a^k$ and $\beta_k:=b^k$ shows $\lbrace a^kb^k : k\ge 0\rbrace$ is not regular.
  2. $\alpha_k:=a^k$ and $\beta_k:=ba^k$ shows the set of palindromes is not regular.
  3. $\alpha_k:=ba^k$ and $\beta_k:=ba^k$ shows $\lbrace ww : w\in\Sigma^*\rbrace$ is not regular.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.