11
$\begingroup$

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?

Improve this question
$\endgroup$

6 Answers 6

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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). $\endgroup$
    – Michael Albert
    Commented Aug 14, 2013 at 4:15
  • $\begingroup$ Sometime between when I left this answer and now I have come around to the same point of view. If we were only teaching about regular languages, I would drop the pumping lemma. But the pumping lemma for regular languages does still have some small use as a warmup to the pumping lemma for context-free languages, where we don't have Myhill–Nerode. $\endgroup$
    – David Eppstein
    Commented Jun 3, 2017 at 4:42
18
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 3
    $\begingroup$ THAT. IS. AWESOME. Where can I read more about this? $\endgroup$
    – Andrew Critch
    Commented Oct 20, 2009 at 4:29
  • 3
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 20, 2009 at 4:47
  • $\begingroup$ Simply awesome. Thanks for making me aware of this. $\endgroup$
    – Andrew Critch
    Commented Oct 20, 2009 at 4:51
  • 1
    $\begingroup$ 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? $\endgroup$
    – Reid Barton
    Commented Oct 20, 2009 at 4:53
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 20, 2009 at 5:04
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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)

Improve this answer
$\endgroup$
5
$\begingroup$

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.
Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .