I have a gap in my knowledge of work in theory done between 1979 (the
publication of Hopcroft and
Ullman) and 1985. 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.
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.
No comments:
Post a Comment