Re: Regular Expression Question...

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

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