Rehash of regular expression question...

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 comp.compilers page.
Search the comp.compilers archives again.