Tue, 14 Dec 1993 18:43:19 GMT

Related articles |
---|

Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14) |

Re: Regular Expression Question... eanders+@CMU.EDU (Eric A. Anderson) (1993-12-15) |

Re: Regular Expression Question... horst@techfak.uni-bielefeld.de (Horst Hogenkamp) (1993-12-15) |

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: | dschieb@muse.CV.NRAO.EDU (Darrell Schiebel) |

Keywords: | lex, theory, question |

Organization: | Compilers Central |

Date: | Tue, 14 Dec 1993 18:43:19 GMT |

I have a question about regular expressions. Given the following

regular expression:

((e | 0) 1*)* e==epsilon

intuitively, it seems like this should denote the same language as:

(0 | 1)*

But how do I prove this (or disprove it if my supposition is wrong), other

than generating two minimal DFAs and showing that they are equal?

I know that * is idempotent, i.e. r** = r*, but I don't see how to

apply this. I can go several ways with the expression:

((e|0)1*)* -> ((e|0)(e|1)*)* -> ((e(e|1)*)|(0(e|1)*))* ->

((e1*)|(01*))* ...

but I haven't been able to get it... Can anyone help?

thanks,

Darrell Schiebel

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.