# 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 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