Ardens Theorm

Arden's Theorem:

One of the applications of Arden's Lemma is, in the conversion of FA to RE.

Statement:

if P and Q are two regular expressions  over Σ  and P does not contain ε then

R= Q+ RP has a unique solution  and it is given by

R=QP*

Prove:

R = Q + RP

= Q + (Q+ RP)P          // repacing R with Q + RP

= Q + QP + RP2

= Q + QP + (Q+ RP)P2

= Q + QP + QP2 + RP3

.

.

.

.

.

= Q +  QP + QP + QP3 + QPn +QPPn+1

=Q(ε + P+P + P3 + Pn +PPn+1  )

= QPn

or

= QP*