**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^{k}t 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_{1}...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.

## No comments:

## Post a Comment