Wed, 15 Dec 1993 15:15:23 GMT

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) |

Newsgroups: | comp.compilers |

From: | "Eric A. Anderson" <eanders+@CMU.EDU> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.