Computational Complexity

Friday, August 08, 2003

 
A New-To-Me Pumping Lemma for Regular Languages

Posted by Lance

I have a gap in my knowledge of work in theory done between 1979 (the publication of Hopcroft and Ullman) and 1985 (when I started graduate school). So every now and then I see a new result from this time that I should have known years ago. Here is an example from the Winter 1982 SIGACT News, a variation of the regular language pumping lemma due to Donald Stanat and Stephen Weiss.

Theorem: If L is regular then there is a positive integer n such that for every string x of length at least n, there are strings u, v and w with v nonempty such that x=uvw and for all strings r and t and integers k≥0, rut is in L if and only if ruv^kt is in L.

What surprises me about this result is that w does not appear in the conclusion and that the initial r could put the finite automaton in any state before it gets to u. Here is a sketch of the proof.

Let s be the number of states of a finite automaton accepting L. Let y_i be the first i bits of x. For any initial state a, y_i will map it to some state b. So one can consider y_i as a function mapping states to states. There are at most s^s such functions so if |x|≥s^s there is an i and a j, i<j such that y_i and y_j represent the same function. We let u=x₁...x_i-1 and v=x_i...x_j-1. The rest follows like the usual pumping lemma.

Using a result of Jaffe, Stanat and Weiss show that this condition is not only necessary but also sufficient to characterize the regular languages.

9:24 AM # 0 comments

Comment Feeds: This Post All