# Automata Conversion of RE to FA

Automata Conversion of RE to FA with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

# 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: Next TopicArden's Theorem