# Re: Regular Expression Question...

## "Eric A. Anderson" <eanders+@CMU.EDU>Wed, 15 Dec 1993 15:15:23 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)
| List of all articles for this month |

 Newsgroups: comp.compilers From: "Eric A. Anderson" Keywords: lex, DFA, theory Organization: Senior, Math/Computer Science, Carnegie Mellon, Pittsburgh, PA References: 93-12-062 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:
(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
--

Post a followup to this message