|Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14)|
|Rehash of regular expression question... firstname.lastname@example.org (1994-02-18)|
|Re: Rehash of regular expression question... email@example.com (1994-02-21)|
|Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24)|
|From:||Joe Hummel <jhummel@cy4.ICS.UCI.EDU>|
|Organization:||UC Irvine, Department of ICS|
|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 :-)
Return to the
Search the comp.compilers archives again.