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:
Step 2:
Step 3:
Step 4:
Step 5:
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:
Step 2:
Step 3:
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:
Step 2:
Step 3:
Step 4:
