Construction of an FA from an RE - Automata Theory

How to construct an FA from an RE?

Thompson's Construction is used to find out a Finite Automaton from a Regular Expression. You need to minimize the regular expression into more minimum regular expressions and convert these expressions in to NFA and finally to DFA.
Here are some basic RA expressions are the following −

Case 1 − For a regular expression ‘a’, we can construct the following FA −

Case 2 − For a regular expression ‘ab’, we can construct the following FA −
Case 3 − For a regular expression (a+b), we can construct the following FA −
Case 4 − For a regular expression (a+b)*, we can construct the following FA −


Step 1 Let’s construct an NFA with Null moves from the available regular expression.
Step 2 Now remove Null transition from the NFA and change it in to its equivalent DFA.


Let’s convert the following RA into its equivalent DFA − 1 (0 + 1)* 0


We will concatenate three expressions "1", "(0 + 1)*" and "0"
You can remove the ε transitions. Once you remove the εtransitions from the NDFA, we get the following −
It is also called as an NDFA related to the RE − 1 (0 + 1)* 0. If you want to change it into a DFA, then you can usually apply the method of converting NDFA to DFA discussed in Chapter 1.

Finite Automata with Null Moves (NFA-ε)

A Finite Automaton with null moves (FA-ε) will not transit after giving input from the alphabet set and it can also transit without any input symbol. This is called as null move where the transition without input.
An NFA-ε is presented formally by a 5-tuple (Q, ∑, δ, q0, F), which includes
  • Q − a finite set of states
  • ∑ − a finite set of input symbols
  • δ − a transition function q
  • q0 − an initial state q0 ∈ Q
  • F − a set of final state/states of Q (F⊆Q).
The above (FA-ε) accepts a string set − {0, 1, 01}

Removal of Null Moves from Finite Automata

Let’s assume that if in an NDFA, there is a ϵ-move between vertex X to vertex Y, use following steps to remove it.−
  • Find all the outgoing edges from Y.
  • Copy all these edges starting from X without changing the edge labels.
  • If X is an initial state, make Y also an initial state.
  • If Y is a final state, make X also a final state.


Now convert the following NFA-ε to NFA without Null move.


Step 1
See the ε transition is between q1 and q2, so let q1 is Xand qf is Y.
Here the outgoing edges from qf is to qf for inputs 0 and 1.
Step 2 −
Here you need to copy all these edges from q1 without converting the edges from qf and get the following FA −
Step 3 −
Here q1 is referred as an initial state, so we make qf also an initial state.
So the FA becomes −
Step 4 −
Here qf is a final state, so we make q1 also a final state.
So the FA becomes −

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd Protection Status

Automata Theory Topics