DFA to Regular Expression-
The two popular methods for converting a given DFA to its regular expression are-
- Arden’s Method
- State Elimination Method
In this article, we will discuss Arden’s Theorem.
Arden’s Theorem-
Arden’s Theorem is popularly used to convert a given DFA to its regular expression.
It states that-
Let P and Q be two regular expressions over ∑.
If P does not contain a null string ∈, then-
R = Q + RP has a unique solution i.e. R = QP*
Conditions-
To use Arden’s Theorem, following conditions must be satisfied-
- The transition diagram must not have any ∈ transitions.
- There must be only a single initial state.
Steps-
To convert a given DFA to its regular expression using Arden’s Theorem, following steps are followed-
Step-01:
- Form a equation for each state considering the transitions which comes towards that state.
- Add ‘∈’ in the equation of initial state.
Step-02:
Bring final state in the form R = Q + RP to get the required regular expression.
Important Notes-
Note-01:
Arden’s Theorem can be used to find a regular expression for both DFA and NFA.
Note-02:
If there exists multiple final states, then-
- Write a regular expression for each final state separately.
- Add all the regular expressions to get the final regular expression.
Also Read- State Elimination Method
PRACTICE PROBLEMS BASED ON CONVERTING DFA TO REGULAR EXPRESSION-
Problem-01:
Find regular expression for the following DFA using Arden’s Theorem-
Solution-
Step-01:
Form a equation for each state-
- A = ∈ + B.1 ……(1)
- B = A.0 ……(2)
Step-02:
Bring final state in the form R = Q + RP.
Using (1) in (2), we get-
B = (∈ + B.1).0
B = ∈.0 + B.1.0
B = 0 + B.(1.0) ……(3)
Using Arden’s Theorem in (3), we get-
B = 0.(1.0)*
Thus, Regular Expression for the given DFA = 0(10)*
Problem-02:
Find regular expression for the following DFA using Arden’s Theorem-
Solution-
Step-01:
Form a equation for each state-
- q1 = ∈ ……(1)
- q2 = q1.a ……(2)
- q3 = q1.b + q2.a + q3.a …….(3)
Step-02:
Bring final state in the form R = Q + RP.
Using (1) in (2), we get-
q2 = ∈.a
q2 = a …….(4)
Using (1) and (4) in (3), we get-
q3 = q1.b + q2.a + q3.a
q3 = ∈.b + a.a + q3.a
q3 = (b + a.a) + q3.a …….(5)
Using Arden’s Theorem in (5), we get-
q3 = (b + a.a)a*
Thus, Regular Expression for the given DFA = (b + aa)a*
Problem-03:
Find regular expression for the following DFA using Arden’s Theorem-
Solution-
Step-01:
Form a equation for each state-
- q1 = ∈ + q1.b + q2.a ……(1)
- q2 = q1.a + q2.b ……(2)
Step-02:
Bring final state in the form R = Q + RP.
Using Arden’s Theorem in (2), we get-
q2 = q1.a.b* …….(3)
Using (3) in (1), we get-
q1 = ∈ + q1.b + q1.a.b*.a
q1 = ∈ + q1.(b + a.b*.a) …….(4)
Using Arden’s Theorem in (4), we get-
q1 = ∈.(b + a.b*.a)*
q1 = (b + a.b*.a)*
Thus, Regular Expression for the given DFA = (b + a.b*.a)*
Problem-04:
Find regular expression for the following DFA using Arden’s Theorem-
Solution-
Step-01:
Form a equation for each state-
- q1 = ∈ + q1.a + q3.a ……(1)
- q2 = q1.b + q2.b + q3.b ……(2)
- q3 = q2.a …….(3)
Step-02:
Bring final state in the form R = Q + RP.
Using (3) in (2), we get-
q2 = q1.b + q2.b + q2.a.b
q2 = q1.b + q2.(b + a.b) …….(4)
Using Arden’s Theorem in (4), we get-
q2 = q1.b.(b + a.b)* …….(5)
Using (5) in (3), we get-
q3 = q1.b.(b + a.b)*.a …….(6)
Using (6) in (1), we get-
q1 = ∈ + q1.a + q1.b.(b + a.b)*.a.a
q1 = ∈ + q1.(a + b.(b + a.b)*.a.a) …….(7)
Using Arden’s Theorem in (7), we get-
q1 = ∈.(a + b.(b + a.b)*.a.a)*
q1 = (a + b.(b + a.b)*.a.a)*
Thus, Regular Expression for the given DFA = (a + b(b + ab)*aa)*
Also Read- Minimization of DFA
To gain better understanding about Arden’s Theorem,
Next Article- Non-Deterministic Finite Automata
Get more notes and other study material of Theory of Automata and Computation.
Watch video lectures by visiting our YouTube channel LearnVidFun.