Home » Automata Conversion of RE to FA

Automata Conversion of RE to FA

by Online Tutorials Library

Conversion of RE to FA

To convert the RE to FA, we are going to use a method called the subset method. This method is used to obtain FA from the given regular expression. This method is given below:

Step 1: Design a transition diagram for given regular expression, using NFA with ε moves.

Step 2: Convert this NFA with ε to NFA without ε.

Step 3: Convert the obtained NFA to equivalent DFA.

Example 1:

Design a FA from given regular expression 10 + (0 + 11)0* 1.

Solution: First we will construct the transition diagram for a given regular expression.

Step 1:

Conversion of RE to FA

Step 2:

Conversion of RE to FA

Step 3:

Conversion of RE to FA

Step 4:

Conversion of RE to FA

Step 5:

Conversion of RE to FA

Now we have got NFA without ε. Now we will convert it into required DFA for that, we will first write a transition table for this NFA.

State 0 1
→q0 q3 {q1, q2}
q1 qf Ï•
q2 Ï• q3
q3 q3 qf
*qf Ï• Ï•

The equivalent DFA will be:

State 0 1
→[q0] [q3] [q1, q2]
[q1] [qf] Ï•
[q2] Ï• [q3]
[q3] [q3] [qf]
[q1, q2] [qf] [qf]
*[qf] Ï• Ï•

Example 2:

Design a NFA from given regular expression 1 (1* 01* 01*)*.

Solution: The NFA for the given regular expression is as follows:

Step 1:

Conversion of RE to FA

Step 2:

Conversion of RE to FA

Step 3:

Conversion of RE to FA

Example 3:

Construct the FA for regular expression 0*1 + 10.

Solution:

We will first construct FA for R = 0*1 + 10 as follows:

Step 1:

Conversion of RE to FA

Step 2:

Conversion of RE to FA

Step 3:

Conversion of RE to FA

Step 4:

Conversion of RE to FA


You may also like