0
$\begingroup$

I need to prove the equivalence of the following regular expressions:

(cb*c+cb*b)*

(cc)*+(cc)*(cb)(b+c)*

using the following equivalence rules:

• (1) (E + F) + G = E + (F + G)

• (2) E + F = F + E

• (3) E + E = E

• (4) E + ∅ = E

• (5) (EF)G = E(F G)

• (6) Ee = E

• (7) eE = E

• (8) E∅ = ∅

• (9) ∅E = ∅

• (10) E(F + G) = EF + EG

• (11) (F + G)E = F E + GE

• (12) (E*)* = E*

• (13) ∅* = e

• (14) e* = e

• (15) e + E* = E*

• (16) (e + E)* = E*

• (17) e + EE* = E*

• (18) e + E*E = E*

• (19) E*E = EE*

• (20) E*E* = E*

• (21) (EF)*E = E(F E)*

• (22) (E*F*)* = (E + F)*

• (23) (E*F)*E* = (E + F)*

• (24) E*(FE*)* = (E + F)*

• (25) (EF + E)*E = E(F E + E)*

where e denotes the empty word It's possible (but not likely) that some others rules are needed. I know the given expressions are equivalent because I transfoormed them into automata and, with some transformations, I ended with the same. Howver, I'm asked to prove the equivakence using the laws , and none of them seems to be useful. Can someone help me?

$\endgroup$
  • 1
    $\begingroup$ Can you please give more details as to what doesn’t work and where you are stuck? $\endgroup$ – Apoorv Feb 21 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.