DFA to Regular Expression | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Clear all your Computer Science Engineering (CSE) doubts with EduRev Join for Free

Join for Free

Introduction

The two popular methods for converting a DFA to its regular expression are:

• Arden’s Method
• State Elimination Method

State Elimination Method

This method involves the following steps in finding the regular expression for any given DFA
Step 1:

Thumb Rule

The initial state of the DFA must not have any incoming edge.

If there exists any incoming edge to the initial state, then create a new initial state having no incoming edge to it.
Example:

Step 2: 

Thumb Rule

There must exist only one final state in the DFA.

If there exists multiple final states in the DFA, then convert all the final states into non-final states and create a new single final state.
Example:

Step 3:

Thumb Rule

The final state of the DFA must not have any outgoing edge.

Example:

Step 4:

•  Eliminate all the intermediate states one by one.
• These states may be eliminated in any order.

 In the end,

• Only an initial state going to the final state will be left.
• The cost of this transition is the required regular expression.

Note: The state elimination method can be applied to any finite automata.
(NFA, ∈-NFA, DFA etc)

Practice Problems Based on Converting DFA to Regular Expression

Problem 1: Find regular expression for the following DFA

Solution:
Step 1:

• Initial state A has an incoming edge.
• So, we create a new initial state qi.

 The resulting DFA is

Step 2:

• Final state B has an outgoing edge.
• So, we create a new final state qf.

The resulting DFA is

Step 3: Now, we start eliminating the intermediate states.
First, let us eliminate state A.

• There is a path going from state qi to state B via state A.
• So, after eliminating state A, we put a direct path from state qi to state B having cost ∈.0 = 0
• There is a loop on state B using state A.
• So, after eliminating state A, we put a direct loop on state B having cost 1.0 = 10.

Eliminating state A, we get

Step 4: Now, let us eliminate state B.

• There is a path going from state qi to state qf via state B.
• So, after eliminating state B, we put a direct path from state qi to state qf having cost 0.(10)*.∈ = 0(10)*

Eliminating state B, we get

From here,

Regular Expression = 0(10)*

Note: In the above question,

• If we first eliminate state B and then state A, then regular expression would be = (01)*0.
• This is also the same and correct.

Problem 2: Find regular expression for the following DFA

Solution:

Step 1:

•  There exist multiple final states.
• So, we convert them into a single final state.

The resulting DFA is

Step 2: Now, we start eliminating the intermediate states.

First, let us eliminate state q₄.

• There is a path going from state q₂ to state qf via state q₄.
• So, after eliminating state q₄ , we put a direct path from state q₂ to state q_f having cost b.∈ = b.
  

Step 3: Now, let us eliminate state q₃.

• There is a path going from state q₂ to state qf via state q₃.
• So, after eliminating state q₃ , we put a direct path from state q₂ to state qf having cost c.∈ = c.
  

Step 4: Now, let us eliminate state q₅.

• There is a path going from state q₂ to state q_f via state q₅.
• So, after eliminating state q₅ , we put a direct path from state q₂ to state qf having cost d.∈ = d.
  

Step 5: Now, let us eliminate state q₂.

• There is a path going from state q1 to state qf via state q2.
• So, after eliminating state q2 , we put a direct path from state q1 to state qf having cost a.(b+c+d).
  

From here,

Regular Expression = a(b+c+d)