Theory Of Computation

Section B

Identities Related to Regular Expressions

Given R, P, L, Q as regular expressions, the following identities hold:

1. Ø* = ε

2. ε* = ε

3. RR* = R*R

4. R*R* = R*

5. (R*)* = R*

6. RR* = R*R

7. (PQ)*P =P(QP)*

8. (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*

9. R + Ø = Ø + R = R (The identity for union)

10. Rε = εR = R (The identity for concatenation)

11. ØL = LØ = Ø (The annihilator for concatenation)

12. R + R = R (Idempotent law)

13. L (M + N) = LM + LN (Left distributive law)

14. (M + N) L = LM + LN (Right distributive law)

15. ε + RR* = ε + R*R = R*