Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

nfa
dfa
theoretical cs

How to convert NFA to DFA

Ayesha Kanwal

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

NFA vs. DFA

A deterministic finite automaton has one transition from one state to another. On the other hand, a nondeterministic finite automaton has one or more than one transition from one state to another or itself.

Every deterministic finite automaton is a nondeterministic finite automaton but the reverse is not true.

Subset construction method

Assume an NFA for a language L with <Q,Σ,q0,δ,F><Q, Σ, q_0, δ, F> where

  • QQ is the finite set of states
  • ΣΣ is the input symbols
  • q0q_0 is the start state
  • δδ is the transition function
  • FF is the final state

It is converted to a DFA <Q,Σ,q0,δ,F><Q', Σ, q_0, δ', F'> where

  • QQ' is the new finite set of states
  • ΣΣ is the input symbols
  • q0q_0 is the start state
  • δδ' is the transition function
  • FF' is the new final state

Note: While converting an NFA with n states to a DFA, 2n possible set of states can be reachable but not necessarily reached in the DFA.

The following general set of rules are followed to convert a nondeterministic finite automaton to a deterministic finite automaton:

  1. At the beginning QQ' = .
  2. Add q0q_0 to QQ'.
  3. For every state in QQ', find the possible set of states for each input symbol using the transition function of the NFA. If the acquired set of states is not present in QQ', add it.
  4. The final state FF' will be all those states that have FF in them.

Example

Let's consider the following nondeterministic finite automaton that accepts the language {aa,aab}{b}\{{aa, aab}\}^*\{{b}\}.

For this NFA, q0q0 is the start state.

g ENTRY q0 q0 ENTRY->q0 q4 q4 q0->q4   b q1 q1 q0->q1   a q2 q2 q0->q2   a q1->q0   a q3 q3 q2->q3   a q3->q0   b
NFA

δ = Transition Table

state

a

b

q0

q1, q2

q4

q1

q0

-

q2

q3

-

q3

-

q0

q4

-

-

Step 1: Q' is empty

Checks if QQ' is empty.

Step 2: Add the first state to Q'

Add the first state to QQ' such that it now has q0q_0.

Step 3: Find states for each input symbol

For each state in QQ', we will find the states for each of the input symbols. QQ' has q0q_0 presently. Check transitions for 'aa' and 'bb' from the transition table for q0q_0. Update the table as new states are reached.

Step 3.1:
Transition Table for q0

state

a

b

q0

q1, q2

q4

Step 3.2:
Transition Table for {q1,q2} and {q4}

state

a

b

q0

q1, q2

q4

q1, q2

q0, q3

-

q4

-

-

Step 3.3:
Transition Table for {q0,q3}

state

a

b

q0

q1, q2

q4

q1, q2

q0, q3

-

q4

-

-

q0, q3

q1

q0, q4

Step 3.4:
Transition Table for {q1} and {q0, q4}

state

a

b

q0

q1, q2

q4

q1, q2

q0, q3

-

q4

-

-

q0, q3

q1, q2

q4

q1

q0

-

q0, q4

q1, q2

q4

Step 4: Result

Combine all the states in the last obtained transition table and show appropriate transitions. In case a transition is not defined for input, make a transition to the trap state.

For this DFA, q0q0 is the start state.

g ENTRY q0 q0 ENTRY->q0 q0q4 q0q4 q4 q4 q0q4->q4   b q1q2 q1q2 q0q4->q1q2   a trap trap q4->trap   a,b q0->q4   b q0->q1q2   a q1q2->trap   b q0q3 q0q3 q1q2->q0q3   a q1 q1 q1->q0   a q1->trap   b trap->trap   a,b q0q3->q4   b q0q3->q1q2   a
DFA

RELATED TAGS

nfa
dfa
theoretical cs

CONTRIBUTOR

Ayesha Kanwal
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring