*86*

# 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:**