Ardens Theorem in FA|| Finite Automata to Regular expression.

 

In automata finite automata is mathematical model.That mathematical model recognize some set of string or language.To represent certain set of strings in some algebraic manner and describe the language accepted by finite automata is called regular expression.To find out the regular expression recognized by finite automata use Arden Theorem. 

• Given Finite automata.(FA does not null moves and only one initial state).
• Find equation from FA .
• Solve equation using Arden theorem.
• Find the union of all the result obtain for the final state.
• Result corresponding to final state is the final result.

Arden Theorem

if  R and S are two regular expression over an alphabet Σ such that R  does not represent null string.

X=S+XR

X=SR*

X=S+XR

Put the value of X

X=S+(S+XR)R

 X  =S+SR+XR²+-----------

 X  =S(ɛ+R)+XR²

X=SR*

Therefore it is clear that  X=SR* is a solution for arden equation.

X=S+XR

X=S+(SR*)R

X=S+SR*

X=SR*

Putting X=SR* in arden theorem equation satisfied right hand side is equivalent to SR*.Arden equation solution X=SR* which is unique.

Example

Consider Finite Automata find regular Expression using Arden Theorem.

Solution

A=દ+Aa+Ab

B=Aa

C=Ba+Bb

A=દ+A(a+b)

According to the arden theorem S+XR=SR*

A=દ(a+b)*

A=(a+b)*

Put the value of A

B=(a+b)*a

Put the value of  B

C=(a+b)*a(a+b)

C is the final state So regular expression is (a+b)*a(a+b)

So based on Finite Automata  we get regular expression using Arden theorem.