Re: Regular Expression Question...

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:
(0|1)*.


To get the remaining direction, I need one more lemma:
Lemma3: a* = (e|a)a*
Proof:
(e|a)a* = ea* | aa* = a* | aa* = a*, as aa* <= a*.


Then:
(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.
                    -Eric
--

Return to the comp.compilers page.
Search the comp.compilers archives again.