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*

 

  

 

0Comment