Fri, 18 Feb 1994 05:16:08 GMT

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) |

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.