# 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