Arden’s Law

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)

EasyExamNotes © 2023