FLAT Uncategorized

NFA to DFA Conversion (With Expression & Algorithm)

In this post, we will learn how to convert a nfa to dfa. We will also check the algorithms which are used for this conversion and apart from this we will also see some examples. For better understanding, you have to also go through the recommended videos and also check the given pdf. I will try to write this post in details so that it will help you to clear all of your concepts.

A Quick Overview Of This Article,

  • Important Points related to DFA and NFA
  • Difference between DFA and NFA
  • DFA & NFA Representations
  • DFA & NFA examples (Minimization)
  • Conversion of NFA to DFA with the algorithm

Introduction to DFA and NFA

If your concept of NFA or DFA is not clear then firstly I recommend you to go through these YouTube Videos & clear your concept.

–> Quick Overview of NFA – English | Hindi

–> Quick Overview of DFA – English | Hindi

Important points to summarize NFA and DFA,

  • NFA stands for Non-Deterministic Finite Automata where as DFA stands for Non-Deterministic Finite Automata.
  • NFA and DFA both are used in compiler designing process.
  • NFA is as similar as DFA along with some other functionalities as like NFA allows null (ε) value and it have capability to transmit to any other state for any particular input.

Difference Between NFA and DFA

NFA & DFA both are pretty similar in terms of various aspects but there are also some major differences between them are available such as their functionality, backtracking feature, space requirement, etc.

We have differentiated the DFA and NFA in terms of various aspects as like,

  • Their Functions
  • Usability
  • Backtracking Feature
  • Space Requirement

For better understanding please go through this video – Difference Between DFA and NFA.

DFA & NFA Representations

To construct a DFA or NFA, we need to follow certain rules as well as notations. We have to remember certain notations/tuples to construct a DFA or NFA and apart from these rules, there is some certain additionality in NFA as well.

There are some symbols which we follow for the construction of an DFA or NFA,

Lets understand these all notations with an example,

So in the above example,

  • Q is the total number of states which is equal to 3 i.e, Q = { q0 , q1 , q2 }
  • q0 denotes the initial state & any machine can contain one initial state so here q0 is that initial state.
  • Σ contains the input symbols i.e., Σ = {a,b}.
  • F denotes the set of final states i.e., F = { q1 }.
  • δ represents transition function eg., q0 x a -> q1 , q0 x b -> q2.

Conversion of NFA to DFA

To convert an NFA to DFA, we need to follow certain steps. Let’s understand this conversion steps by taking an example.

Please go through the steps by listening the below audio. It will help you to easily understand this conversion.

Didn’t find the audio? Please go here.

Example: Conversion of an NFA (having input a,b that starts with ‘a’) to DFA.

Step 1: Construct an NFA for the given condition

Step 2: Make a state transition table of NFA

Step 3: Now create the sub-equivalent state transition table of DFA with the help of NFA table

Step 4: Construct the DFA using the new DFA table

Some important points to be noted,

  • A DFA must be a complete set.
  • We have to show the output transition equivalent to input transition i.e, a & b.
  • We have created another state “C” because we need to send the output transition of A to another state in case of DFA.
  • An NFA may consist two or more possible next states.

For better understanding please refer KNOWLEDGE GATE lecture video here.