Rehash of regular expression question...

mark@freenet.uwm.edu (Mark Hopkins)
Fri, 18 Feb 1994 05:16:08 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: mark@freenet.uwm.edu (Mark Hopkins)
Keywords: lex, theory
Organization: Compilers Central
References: 93-12-062
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. :)
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.