Regular Expression Question...

dschieb@muse.CV.NRAO.EDU (Darrell Schiebel)
Tue, 14 Dec 1993 18:43:19 GMT

          From comp.compilers
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)
| List of all articles for this month |
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.