Arden’s law is used in simplification of regular expression. It is states as, for p, q and r to be regular expressions, and if ∈ is not member of L(P) then the equation in r as
r = q + rp has a unique solution given by r = qp*
Let us proof that r = qp* is unique solution of equation r = q + rp.
The equation is, r = q + rp…. (i)
by substituting value of ‘r’ equation (i) can be written as
r = q + (q + rp)p
r = q + qp + rp2
r = q + qp + (q + rp) p2
r = q + qp + qp2 + rp3
r = = (q + qp + qp2 +…. qpi) + rpi+1
r = q(∈ + p + p2 +…. + pi) + rpi+1 i ≥ 0
r = qp* (Here p power * means repeatation of p)