Re: Rehash of regular expression question...

Joe Hummel <jhummel@cy4.ICS.UCI.EDU>
Thu, 24 Feb 1994 00:11:07 GMT

          From comp.compilers
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)
| List of all articles for this month |
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.