24 Mar 1996 21:49:28 -0500

Related articles |
---|

Non-deter. regular expr. -> deter. regular expr. faase@cs.utwente.nl (1996-03-20) |

Re: Non-deter. regular expr. -> deter. regular expr. leichter@smarts.com (Jerry Leichter) (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. mtimmerm@microstar.com (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. neumann@PSI.Uni-Trier.DE (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. ikastan@alumnae.caltech.edu (1996-03-24) |

From: | ikastan@alumnae.caltech.edu (Ilias Kastanas) |

Newsgroups: | sci.math,comp.compilers,comp.programming |

Date: | 24 Mar 1996 21:49:28 -0500 |

Organization: | Caltech Alumni Association |

Expires: | March 31, 1996 |

References: | 96-03-125 96-03-152 |

Keywords: | DFA, theory |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.