10
$\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?

$\endgroup$
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.

$\endgroup$
  • 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 Aug 14 '13 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 Jun 3 '17 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.

$\endgroup$
  • 3
    $\begingroup$ THAT. IS. AWESOME. Where can I read more about this? $\endgroup$ – Andrew Critch Oct 20 '09 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 Oct 20 '09 at 4:47
  • $\begingroup$ Simply awesome. Thanks for making me aware of this. $\endgroup$ – Andrew Critch Oct 20 '09 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 Oct 20 '09 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 Oct 20 '09 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.

$\endgroup$
5
$\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)

$\endgroup$
4
$\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.
$\endgroup$
3
$\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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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