Thu, 24 Feb 1994 00:11:07 GMT

Related articles |
---|

Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14) |

Rehash of regular expression question... mark@freenet.uwm.edu (1994-02-18) |

Re: Rehash of regular expression question... dobrien@seas.gwu.edu (1994-02-21) |

Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24) |

Newsgroups: | comp.compilers |

From: | Joe Hummel <jhummel@cy4.ICS.UCI.EDU> |

Keywords: | DFA, theory |

Organization: | UC Irvine, Department of ICS |

References: | 93-12-062 94-02-152 |

Date: | Thu, 24 Feb 1994 00:11:07 GMT |

*>Hum, from Alg class I don't agree that determining if two reg langs*

*>are equal is NP-hard. I believe we can take any regular expression*

*>and convert it to a NFA in P-time. We can take two NFA's and take*

*>their Unions, Compliments and Intersections in P-time. Then we can*

*>create new NFA that is (L1 intersect L2') union (L1' intersect L2).*

*>If L1 = L2 then L3 is empty. We can determine in P-time a NFA/DFA*

*>is empty. Therefore, isn't the problem P, and not NP?*

RE -> NFA can be done in P-time. As for complement, a quick peek at

Hopcroft and Ullman states the following in their construction proof of

complementation: "Note that it is essential to the proof that M is

deterministic and without E moves." The implication of course is that you

must first convert the NFA to a DFA before proceeding with the

construction. Since NFA -> DFA can experience exponential state

explosion, you end up with a problem in NP.

Is there an algorithm to do complementation directly on an NFA in P-Time?

I'd sure like to know if there is :-)

- joe

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.