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 −

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

Method

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.

Problem

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

Solution

We will concatenate three expressions "1", "(0 + 1)*" and "0"
ndfa_with_null_transition_for_ra
You can remove the ε transitions. Once you remove the εtransitions from the NDFA, we get the following −
ndfa_with_null_transition_for_ra1
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).
finite_automata_with_null_moves
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.

Problem

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

Solution

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 −
ndfa_after_step2
Step 3 −
Here q1 is referred as an initial state, so we make qf also an initial state.
So the FA becomes −
ndfa_after_step3
Step 4 −
Here qf is a final state, so we make q1 also a final state.
So the FA becomes −
final_ndfa_without_null_moves

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

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

Automata Theory Topics