|Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14)|
|Rehash of regular expression question... email@example.com (1994-02-18)|
|Re: Rehash of regular expression question... firstname.lastname@example.org (1994-02-21)|
|Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24)|
|From:||email@example.com (David O'Brien)|
|Organization:||George Washington University|
|Date:||Mon, 21 Feb 1994 00:19:20 GMT|
: A while back Darrell Schiebel asked (using a slightly different notation):
: How to prove that ( (1 + a) b* ) = (a + b)*
I assume that the above is suppose to be ((1+a)b*)*
: in regular expression notation, where 1 denotes the empty string.
: Algebraically, one could proceed as follows:
: ( (1 + a) b* )* = (b* + a b*)* distributivity
: = b** (a b* b**)* (X + Y)* = X* (Y X*)*
: = b* (a b* b*)* X** = X*
: = b* (a b*)* X* X* = X*
Isn't the case above X* Y* ? Not X* X*. If so then you
can't do this. If the above is correct, please explain
: Interestingly, the general problem of proving a regular expression
: involving symbols x1, x2, ..., xn equal to (x1 + x2 + ... + xn)* is
: not just NP-hard, but P-space complete (note: P-time <= NP-time <= P-space,
: with equality if P = NP).
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 above problem P, and not NP?
-- David O'Brien (firstname.lastname@example.org)
Return to the
Search the comp.compilers archives again.