Re: Non-deter. regular expr. -> deter. regular expr.

Frans F.J. Faase wrote:
> Is it possible to transform any given non-deterministic regular
> expression into a deterministic regular expression? I know it is


Jerry Leichter <leichter@smarts.com> wrote:
>Note that, just as there's no special reason to describe matching as
>left to right, there's no reason to define it as starting at one end
>or another. You could easily define a matcher that starts at the
>middle of the string and tries to grow outward - going as far as it
>can to the right and then to left; to the left and then to the right;
>one step each in alternating directions; or what have you. For any
>given RE, some of these choices will require non-determinism in the
>"obvious" resulting FSM; some won't. (Of course, we know the
>non-determinism can always be eliminated.)
>
>Query: The basic construction gives you an NFSM whose size (number of
>states) is linear in the size of the input. Converting that DFSM may
>cause an exponential blowup in the number of states. (a) Are there
>examples where the exponential blowup actually occurs, but would *not*
>occur if scanning in some other order were allowed? (b) Are there RE's
>whose expression as a DFSM *always* requires an exponential blowup, no
>matter what order you allow scanning in? (I'd guess the answer to (b)
>is yes. I suppose one might call such an RE "non-deterministic"!)






One might call it something worse, too! They are not really
nondeterministic, but they can be quite intractable. Early complexity
theory results: If squaring (E^2 = EE) is allowed in RE's, the empty
complement problem requires exponential space If "(string) length
expressions" are allowed, emptiness is "super-exponential" (beyond any
stack of exponentials; the problem is not Kalmar-elementary).


For usual RE's the parsimonious approach is not to build the DFA
outright but to "explore" the subset construction, launching recursive
calls and re-using space. Empty complement is then in low PSPACE, in
DSPACE(n^2) -- n bounding the number of states in the NFA (and the
length of the RE).




If we do want the DFA, there are standard examples where its number of
states is exponential in n. Usually that is: looking for the first
occurrence of an alphabet symbol. Enough to bury you in red tape.




I think, off the cuff, that for a) and b) above we must specify what
sort of scanning is meant. It does seem (b) is true; if only finitely
many scanning methods exist we could shuffle around accordingly a
number of disjoint copies of the counterexample.


There is an example with _2-way FA's_ where the minimal DFA has an
exponential number of states.


For (a) we could use binary strings whose n-th bit from the end is 1.
A DFA has to keep track of the most recent n bits seen; an NFA guesses
nondeterministically which input bit is the n-th from th end. If
scanning is changed into end-to-start, the task becomes trivial.




Ilias








--

Return to the comp.compilers page.
Search the comp.compilers archives again.