# Re: Regular Expression Question...

## Horst Hogenkamp <horst@techfak.uni-bielefeld.de>Wed, 15 Dec 1993 16:56:16 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: Horst Hogenkamp Keywords: lex, theory Organization: Universitaet Bielefeld, Technische Fakultaet. References: 93-12-062 Date: Wed, 15 Dec 1993 16:56:16 GMT

dschieb@muse.CV.NRAO.EDU (Darrell Schiebel) writes:
> [...] 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), [...]

You need the following rules:

R0: ee == e
R1: (x|y)z == xz|yz
R2: x(y|z) == xy|xz
R3: ex == x
R4: xe == x
R5: x* == e|x*
R6: x* == (e|x)*
R7: x* == x|x*
R8: (x|(y|z)) == (x|y|z)
R9: (x|y|xy)* == (x|y)*

Here we go:

((e|0)1*)*
= ( e 1* | 0 1* )* (R1)
= ( 1* | 0 1* )* (R3)
= ( e | 1* | 0 1* )* (R5+R8)
= ( e | 1 | 1* | 0 1* )* (R7+R8)
= ( e | 1 | 1* | 0(e| 1*))* (R5)
= ( e | 1 | 1* | 0 e|01* )* (R2)
= ( e | 1 | 1* | 0 |01* )* (R4)
= ( 1 | 0 )* (R9)

The problem might be to prove R9, but:

(x|y)* = ( (e|x) | (e|y) )* (R6)
= ( (e|x)e | (e|x)y )* (R2)
= ( ee | xe | ey | xy )* (R1)
= ( e | x | y | xy )* (R0+R4+R3)
= ( x | y | xy )* (R6+R8)

I hope this is right.

Horst.
--

Post a followup to this message