Arden's Theorem

Arden's Theorem is basically used to find out regular expression with properties of a Finite Automaton. The Arden's Theorem is also called Arden's Lemma. It is a mathematical statement. As we know, a language is a set of strings. These sets can be specified by the meaning of some language expression. This is evaluated by language operations. It is valuable for checking the equivalence of two regular expressions along with the conversion of DFA to a regular expression.



Application of Arden Theorem

The main applications of Arden's Theorem are as follows:

  • To determine the regular expression of finite automata.
  • It helps in checking the equivalence of two regular expressions.


Statement

Suppose, an alphabet Σ having two regular expressions P and Q. If P does not contain a null string, then -

R=Q+RP
has a unique solution that is -
R=QP∗

It means, whenever the equation is in the form of R=Q+RP, we can directly replace this with R=QP∗.


Proof of Arden's Theorem

Here, we have proved that R=QP∗ is the unique solution of R=Q+RP.

R=Q+RP

R=Q+[Q+RP]P 

// Put R = Q+RP 
R = Q + QP + RPP 

// Let's put the value R = Q+RP, repeatedly in place of R 
R = Q + QP +[Q+RP]PP 
R = Q + QP + QPP + RPPP 
R = Q + QP + QP2 + QP3 + QP4 + .. .. 
R = Q(1 + P + P2 + P3 + ….) 

// Hence Proved
R = QP∗




Example of Arden's Theorem

Here is the following DFA state diagram, we will construct the regular expression using Arden's theorem-

Arden's Theorem

The state equations of the above DFA are-

A = ∈ + A0 + B0 
B = A1 + B1 

//substitute the value of B 
B = A1 + (A1 + B1)1 
B = A1 + A11 + B11 

//.. Arden's theorem
B = A11*

Now, substitute the value for B in A -

A = ∈ + A0 + B0 
A = ∈ + A0 + (A11*)0 
A = ∈ + A0 + A11*0 
A = ∈ + A(0 + 11*0) 

//..Using Arden's theorem 
A = ∈(0 + 11*0)* 

// Hence Proved
A = (0 + 11*0)*