|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)|
|From:||"Eric A. Anderson" <eanders+@CMU.EDU>|
|Keywords:||lex, DFA, theory|
|Organization:||Senior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA|
|Date:||Wed, 15 Dec 1993 15:15:23 GMT|
dschieb@muse.CV.NRAO.EDU (Darrell Schiebel) writes:
> 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?
In all of these, a,b,c represent parenthisized (if neccesary) reg. exprs.
Defn.: >= means is a superset of. (<= means subset)
Lemma1: (a*) = (e|a|aa|...) >= (e|a)
Lemma2: (a|b|c) >= (a|b)
Then working with the inner construct:
(e|0)1* >=[lemma1] (e|0)(e|1) =[distrib] (ee|e1|0e|01) =
=[collapse e] (e|0|1|01) >=[lemma2 & associativity ] (0|1)
Which can then be substituted into the * to get:
To get the remaining direction, I need one more lemma:
Lemma3: a* = (e|a)a*
(e|a)a* = ea* | aa* = a* | aa* = a*, as aa* <= a*.
(0|1)* = ((0|1)*)* >=[lemma3] ((e|(0|1))(0|1)*)* = [associative]
((e|0|1)(0|1)*)* >= [lemma2] ((e|0)(0|1)*)*
>= ((e|0)(1)*)* = ((e|0)1*)*.
So I have (0|1)* >= ((e|0)1*)*, and ((e|0)1*)* >= (0|1)*, and
so by double inclusion (0|1)* = ((e|0)1*)*
Where = has to mean, indeed all of =,>=.<=, that the language
generated by the regular expressions are equal.
Return to the
Search the comp.compilers archives again.