Arden’s Theorem State, Proof and application

Arden’s Theorem:

In order to find out a regular expression (RE) of a Finite Automaton, we have one another method to use i.e. Arden’s Theorem along with the properties of regular expressions.

Statement:

Let P and Q be two regular expressions over input alphabet ∑. If P does not contain null string ε, then the equation
R = Q + RP                  ———–  (1)
has a unique solution that is;
R = QP*                       ———–  (2)

Proof:

Let us verify whether QP* is a solution to the equation.
R = Q + RP
On substitution of QP* for R in Equation (1)
R = Q + RP      =          Q + RP
=          Q* (ε + P*P) = QP*
Thus the equation (1) satisfied by R = QP*. We still do not know whether QP* is a unique solution or not.
To establish uniqueness, we expand it by putting the value of R recursively again and again, we get the following equation;

                                    R = Q + RP
R = Q + (Q + RP)P                   [∵ R = Q + RP]
= Q + QP + RP²
= Q + QP + (Q + RP)P²
= Q + QP + QP² + RP³
⋮
= Q + QP + QP² + … + QPⁱ + RPⁱ⁺¹
                                        =  Q (ε + P + P² + P³ + …. + Pⁱ) + RPⁱ⁺¹         ———–  (3)

Here, i is any arbitrary integer.
Let us take a string ω ∈ R | length of ω = k. Substituting k for i in equation (3) we get;
=  Q (ε + P + P² + P³ + …. + P^k) + RP^k+1
Since P does not contain ε, ω is not contained in RP^k+1 as the shortest string generated form RP^k+1 will have a length of k+1.
Since ω is contained in R it must be contained in Q (ε + P + P² + P³ + …. + P^k).
Conversely, if ω is contained in QP* then for some integer k it must be in Q (ε + P + P² + P³ + …. + P^k), and hance in R = Q + QP.
Hence, proved.

Application of Arden Theorem:

The main application of Arden’s Theorem are as following;

• It helps to determine the regular expression of finite automata.
• Arden’s theorem helps in checking the equivalence of two regular expressions.