|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... email@example.com (Horst Hogenkamp) (1993-12-15)|
|Rehash of regular expression question... firstname.lastname@example.org (1994-02-18)|
|Re: Rehash of regular expression question... email@example.com (1994-02-21)|
|Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24)|
|From:||dschieb@muse.CV.NRAO.EDU (Darrell Schiebel)|
|Keywords:||lex, theory, question|
|Date:||Tue, 14 Dec 1993 18:43:19 GMT|
I have a question about regular expressions. Given the following
((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)*))* ->
but I haven't been able to get it... Can anyone help?
Return to the
Search the comp.compilers archives again.