Converting Finite Automata to Regular Expression using Arden’s Theorem
Converting Finite Automata to Regular Expression using Arden’s Theorem
The Arden’s Theorem can be applied to find the regular expression recognized by the given transition diagram. This theorem can be applied to transition diagram not containing ?-moves or ?-transitions. Let’s first understand the Arden’s Theorem.
Arden’s Theorem
Let P, Q, and R be three Regular Expressions over ?. If P does not contain ? then the equation R= Q + RP has a unique solution given by R = QP*
Proof:
We have R = Q + RP* ……….Eq (1)
and R = QP*
Substitute R = QP* in (1) we get.
R = Q + (QP*) P
= Q + QP*P
= Q (? + P*P)
= QP* (by using identity ? + R*R = R*)
Thus R = QP* is a solution of R = Q + RP
Example 1
Find the regular expression equivalent to the following transition diagram.
Solution:
The above transition diagram does not contain ?-moves or transitions. So, we apply Arden’s Theorem method to find the regular expression.
The equation corresponding to state q0 and q1 is shown below:
q0 = q0b + ? …………. (1)
q1 = q0a + q1a + q1b ……………… (2)
In given transition diagram q1 is the final state. So, the resulting regular expression will be equal to q1.
From eq (2) we have:
q1 = q0a + q1a + q1b
q1 = q0a + q1 (a + b)
q1 = q0a (a + b)*
(by using Arden’s Theorem, if R = Q + RP then R = QP* ) ……………… (3)
From equation (1), we have
q0 = q0b + ?
q0 = ?b*
q0 = b* (using Arden’s Theorem)
Substituting the value of q0 = b* in equation (3) we get,
q1 = b*a (a + b)*
Hence the final Regular Expression equivalent to the given transition diagram is:
Regular Expression = b*a (a + b)*.
Example 2
Find the regular expression equivalent to the following transition diagram.
Solution:
The above transition diagram does not contain ?-moves or transitions. So, we apply Arden’s Theorem method to find the regular expression.
The equations corresponding to state q0, q1 and q2 is shown below:
q0 = q0b + ? …………. (1)
q1 = q0a + q1b + q2a ……………… (2)
q2 = q1a ……………… (3)
In given transition diagram, q1 and q2 are the final states. So, the final resulting regular expression will be equal to the sum of both the regular expressions.
From equation (1), we have
q0 = q0b + ?
q0 = ?b*
q0 = b* (using Arden’s Theorem)
Substituting the value of q0 and q2 in equation (2), we get ………………….. (4)
q1 = q0a + q1b + q2b a
q1 = b*a + q1b + q1aa
q1 = b*a + q1 (b + aa)
q1 = b*a (b + aa)* …………………… (5)
Substituting the value of q1 from equation (5) to equation (3), we get
q2= q1a
q2 = b*a (b + aa)*a
Hence the final Regular Expression equivalent will be equivalent to:
Regular Expression = q1 + q2 = b*a (b + aa)* + b*a (b + aa)*a
Example 3
Find the regular expression equivalent to the following transition diagram.
Solution:
The above transition diagram does not contain ?-moves or transitions. So, we apply Arden’s Theorem method to find the regular expression.
The equations corresponding to state q0, q1 and q2 is shown below:
q0 = q0a + ? …………. (1)
q1 = q0b + q1b ……………… (2)
q2 = q1 (a +b) + q2 (a + b) ……………… (3)
In given transition diagram q0 and q1 are the final state. So, the final resulting regular expression will be equal to the sum of both the regular expressions.
From equation (1), we have
q0 = q0a + ?
q0 = ? a*
q0 = a* (using Arden’s Theorem) ………………….. (4)
by substituting the value of q0 in equation (2), get
q1 = q0b + q1b
q1 = a*b + q1b
q1 = a*bb*
q0 + q1 = a* + a*bb*
= a*(? + bb*)
= a*b* ( by using identity ? + RR* = R*)
Hence the final Regular Expression equivalent to the given transition diagram is
Regular Expression = a*b*.