Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] A New-To-Me pumping lemma for Regular Languages

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Aug 8, 2003
    • 0 Attachment
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.