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 string. These sets can be specified by 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.

Suppose, an alphabet Σ having two regular expressions P and Q. If P does not contain 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)*





Read more articles


General Knowledge



Learn Popular Language