[My Computational Complexity Web Log] A New-To-Me pumping lemma for Regular Languages
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 ruvkt 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 yi be the first i bits of x. For any initial state a, yi will map it to some state b. So one can consider yi as a function mapping states to states. There are at most ss such functions so if |x|≥ss there is an i and a j, i<j such that yi and yj represent the same function. We let u=x1...xi-1 and v=xi...xj-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.
Posted by Lance Fortnow to My Computational Complexity Web Log at 8/8/2003 10:24:11 AM
Powered by Blogger Pro