|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 (Mark Hopkins)|
|Date:||Fri, 18 Feb 1994 05:16:08 GMT|
A while back Darrell Schiebel asked (using a slightly different notation):
How to prove that ( (1 + a) b* ) = (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*
= (a + b)* same reason as line 2
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).
Another way to prove them equal is to run both expressions through my
regular expression converter (using | in place of +) and see what happens. :)
Return to the
Search the comp.compilers archives again.