PadhaikoAll subjects

NFA, ε-NFA & Their Equivalence with DFA

Theory of Computation (ENCT 203)

Open in the Padhaiko app

2.2.2 Non-Deterministic Finite Automata (NDFA or NFA)

Definition

Non-Deterministic Finite Automaton (NDFA / NFA)

A Non-Deterministic Finite Automaton (NDFA or NFA) is a finite automaton in which the next state is only partially determined by the current state and input symbol:

Formally, a general non-deterministic finite automaton is a 5-tuple (quintuple)

where:

For example, the following 3-state NFA over accepts all strings ending in ab. When in state upon reading a, it can either remain in or move to ; if it is in and reads a, that branch has no outgoing transition and halts:

2.2.2 Non-Deterministic Finite Automata (NDFA or NFA)NFA
2.2.2 Non-Deterministic Finite Automata (NDFA or NFA) a, b a b q0 q1 q2
Stateab
→q0{q0, q1}{q0}
q1∅{q2}
*q2∅∅

Practical Applications of NDFAs

Even though every NDFA can be converted into an equivalent DFA, NDFAs are widely used because they are often exponentially more compact and far easier to construct directly from specifications:

  1. Digital Circuit Design & Verification: Software for designing and checking the behavior of sequential digital circuits and concurrent protocols.
  2. Compiler Lexical Analyzers: Regular expressions describing programming-language tokens are first compiled into NDFAs before subset construction builds the scanner table.
  3. Large-Scale Text Scanning: Searching large collections of text (such as indexing web pages or multi-pattern intrusion detection) for multiple patterns simultaneously.
  4. Formal Verification Systems: Model-checking software for verifying finite-state hardware and communication systems.
AspectDeterministic Finite Automaton (DFA)Non-Deterministic Finite Automaton (NFA)
Next-State UniquenessFor each , there is exactly one next state .For each , there may be zero, one, or multiple next states in .
Transition Signature. (or ).
Empty-String () MovesNot allowed (-transitions cannot occur).Allowed in an -NFA without consuming input.
Acceptance ConditionThe unique computation path for ends in .At least one computation path for ends in .
State Count & ComplexityMay require up to states to simulate an -state NFA, but processes a string of length in deterministic steps.Often much smaller ( states) and easier to design, though tracking all active states takes time unless converted to a DFA.

Worked Out Examples on NFA Design (Book Examples 2.7–2.9)

Example 2.7

NDFA for Strings Containing 'bb' or 'bab'

Design a non-deterministic finite automaton (NDFA) that accepts the set of strings over containing an occurrence of the pattern bb or of the pattern bab.

Define the 5-tuple and states

Let with , , , and :

  • loops on and until it non-deterministically guesses the start b of either bb or bab (moving to ).
  • From , reading b reaches (completing bb, which transitions via to ), while reading a reaches (matching ba, which transitions on b to ).
Transition table and state diagram (with -transition)
State
Worked Out Example 2.7 — NDFA for Strings Containing 'bb' or 'bab'ε-NFA
Worked Out Example 2.7 — NDFA for Strings Containing 'bb' or 'bab' a, b a, b b b a ε a b q0 q1 q2 q3 q4
Stateabε
→q0{q0}{q0, q1}∅
q1{q3}{q2}∅
q2∅∅{q4}
q3{q0}{q4}∅
*q4{q4}{q4}∅
  • Machine-checked
  • ✓ accepts bb
  • ✓ accepts bab
  • ✓ accepts abb
  • ✓ accepts ababa
  • ✓ accepts bbab
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects aba
  • ✓ rejects baa
Alternative NFA without -transitions

Eliminating the -move from to makes both and accepting trap states ():

State
Worked Out Example 2.7 — NDFA for Strings Containing 'bb' or 'bab'NFA
Worked Out Example 2.7 — NDFA for Strings Containing 'bb' or 'bab' a, b a, b a, b b b a a b q0 q1 q2 q3 q4
Stateab
→q0{q0}{q0, q1}
q1{q3}{q2}
*q2{q2}{q2}
q3{q0}{q4}
*q4{q4}{q4}
  • Machine-checked
  • ✓ accepts bb
  • ✓ accepts bab
  • ✓ accepts abb
  • ✓ accepts ababa
  • ✓ accepts bbab
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects aba
  • ✓ rejects baa
Answer:

(or with ).

Example 2.8

NDFA for Regular Expression r = b*ab

Design a non-deterministic finite automaton (NDFA) for the regular expression .

Define the 5-tuple and transition table

Let where , , , and :

State
Draw the state diagram and trace on 'bbab'
Worked Out Example 2.8 — NDFA for Regular Expression r = b*abNFA
Worked Out Example 2.8 — NDFA for Regular Expression r = b*ab b a b q0 q1 q2
Stateba
→q0{q0}{q1}
q1{q2}∅
*q2∅∅
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts bab
  • ✓ accepts bbab
  • ✓ accepts bbbab
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ba
  • ✓ rejects aba
  • ✓ rejects abb

Testing for the string "bbab":

Answer:

with .

Example 2.9

DFA and NFA for Regular Expression (ab ∪ aba)*

Design a DFA (and corresponding NFA) for the regular expression .

Construct the 5-state DFA

Let with , , , and :

  • : start state (, accepting).
  • : read a at the beginning of a block ab or aba.
  • : read ab (accepting; reading a next moves to since that a may either complete aba or start a new block).
  • : read aba (accepting; reading a next means aba finished and a new block started at , whereas reading b next means the previous block was ab and we just completed another ab at ).
  • : dead state.
Worked Out Example 2.9 — DFA and NFA for Regular Expression (ab ∪ aba)*DFA
Worked Out Example 2.9 — DFA and NFA for Regular Expression (ab ∪ aba)* a, b a b b a a b a b q0 q1 q4 q2 q3
Stateab
→*q0q1q4
q1q4q2
q4q4q4
*q2q3q4
*q3q1q2
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts ab
  • ✓ accepts aba
  • ✓ accepts abab
  • ✓ accepts abaab
  • ✓ accepts ababaab
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aa
  • ✓ rejects abb
  • ✓ rejects baba
Construct the compact 3-state NFA

Using non-determinism, we need only 3 states with and : from , reading a moves to ; from , reading b either returns directly to (completing ab) or moves to , which returns to on a (completing aba):

Worked Out Example 2.9 — DFA and NFA for Regular Expression (ab ∪ aba)*NFA
Worked Out Example 2.9 — DFA and NFA for Regular Expression (ab ∪ aba)* a b b a q0 q1 q2
Stateab
→*q0{q1}∅
q1∅{q0, q2}
q2{q0}∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts ab
  • ✓ accepts aba
  • ✓ accepts abab
  • ✓ accepts abaab
  • ✓ accepts ababaab
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aa
  • ✓ rejects abb
  • ✓ rejects baba
Answer:

The DFA has 5 states with , while the equivalent NFA requires only 3 states with .


2.3 Equivalence of DFA and NFA (Subset Construction)

Theorem

Equivalence of NFA and DFA (Rabin–Scott Subset Construction)

For every non-deterministic finite automaton with states, there exists an equivalent deterministic finite automaton with at most states such that .

Subset Construction Procedure:

  1. Initial State of DFA: Set the start state of to the singleton subset and compute for every .
  2. Subset Expansion: For each newly discovered subset state and each input symbol , compute

(If the union is empty, it transitions to the dead/empty-set state , which loops to itself on all symbols.)

  1. Termination & Final States: Repeat until no new subsets of are generated. A subset state is an accepting state of () if and only if (i.e., contains at least one accepting state of ).
Example 2.10

Convert NFA to Equivalent DFA

Convert the following NFA into an equivalent DFA:

Worked Out Example 2.10 — Convert NFA to Equivalent DFANFA
Worked Out Example 2.10 — Convert NFA to Equivalent DFA b b a b q0 q1 q2
Stateba
→q0{q0}{q1}
q1{q1, q2}∅
*q2∅∅
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts bab
  • ✓ accepts abb
  • ✓ accepts babb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aba
  • ✓ rejects ba
Evaluate transitions from the start subset

Let be the transition function of the DFA and be the transition function of the NFA. Starting from :

Evaluate transitions for new subsets and

For :

For :

Construct the DFA transition table and state diagram

Denoting the subset states as q0 , q1 , q12 (accepting, since ), and phi :

DFA State
(q0)
(q1)
(q12)
(phi)
Worked Out Example 2.10 — Convert NFA to Equivalent DFADFA
Worked Out Example 2.10 — Convert NFA to Equivalent DFA a, b b b a b a a q0 q1 q12 phi
Stateba
→q0q0q1
q1q12phi
*q12q12phi
phiphiphi
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts bab
  • ✓ accepts abb
  • ✓ accepts babb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aba
  • ✓ rejects ba
Answer:

The equivalent DFA has states , start state , and sole accepting state .


2.4 Conversion of ε-NFA to DFA and ε-NFA to NFA

Definition

ε-Closure and Conversion of ε-NFA

An -NFA is an NFA that permits transitions on the empty string without consuming any input symbol.

  1. Any subset state containing an accepting state of the -NFA () is an accepting state of the DFA.

and mark a state as accepting in the NFA if .

Example 2.11

Convert ε-NFA to DFA

Convert the following -NFA into an equivalent DFA:

Worked Out Example 2.11 — Convert ε-NFA to DFAε-NFA
Worked Out Example 2.11 — Convert ε-NFA to DFA a b a ε ε q0 q1 q2
Stateabε
→q0{q0}∅{q1}
q1∅{q1}{q2}
*q2{q2}∅∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts aabba
  • ✓ rejects bbab
  • ✓ rejects bab
Compute the -closure of every state
Compute for each reachable subset state

For :

For :

For :

Construct the DFA transition table and state diagram

Writing q012 , q12 , q2 , and phi (all three non-empty subsets contain and are accepting):

State
(q012)
(q12)
(q2)
(phi)
Worked Out Example 2.11 — Convert ε-NFA to DFADFA
Worked Out Example 2.11 — Convert ε-NFA to DFA a, b a b a b a b q012 q12 q2 phi
Stateab
→*q012q012q12
*q12q2q12
*q2q2phi
phiphiphi
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts aabba
  • ✓ rejects bbab
  • ✓ rejects bab
Answer:

The equivalent DFA has start state and accepting states (recognizing ).

Example 2.12

Convert 5-State ε-NFA to DFA

Convert the following -NFA into an equivalent DFA:

Worked Out Example 2.12 — Convert 5-State ε-NFA to DFAε-NFA
Worked Out Example 2.12 — Convert 5-State ε-NFA to DFA ε b a ε ε a b a ε q0 q1 q2 q3 q4
Statebaε
→q0{q2}∅{q1}
q1∅{q0, q4}{q2, q3}
q2{q4}∅∅
q3∅{q4}∅
*q4∅∅{q3}
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts aa
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts bb
  • ✓ accepts aba
  • ✓ accepts abb
  • ✓ rejects ε
  • ✓ rejects bbba
  • ✓ rejects bab
Compute the -closure of each state

Following the -edges , , , and :

Evaluate on reachable subset states
  • From :
  • From :
  • From :
  • From :
Construct the DFA transition table and state diagram

Let q0123 , q01234 , q234 , q34 , and phi :

State
(q0123)
(q01234)
(q234)
(q34)
(phi)
Worked Out Example 2.12 — Convert 5-State ε-NFA to DFADFA
Worked Out Example 2.12 — Convert 5-State ε-NFA to DFA a, b a a a b b a, b b q0123 q01234 q234 q34 phi
Stateab
→q0123q01234q234
*q01234q01234q234
*q234q34q34
*q34q34phi
phiphiphi
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts aa
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts bb
  • ✓ accepts aba
  • ✓ accepts abb
  • ✓ rejects ε
  • ✓ rejects bbba
  • ✓ rejects bab
Answer:

The equivalent DFA has start state and accepting states , , and .

Example 2.13

Convert ε-NFA to NFA (Remove ε-Transitions)

Convert the following -NFA into an equivalent NFA without -transitions:

Worked Out Example 2.13 — Convert ε-NFA to NFA (Remove ε-Transitions)ε-NFA
Worked Out Example 2.13 — Convert ε-NFA to NFA (Remove ε-Transitions) 0 ε ε 0 1 1 0 A B D C E
State01ε
→A{A}∅{B, D}
B{C}{E}∅
D{E}∅∅
C∅{B}∅
*E∅∅∅
  • Machine-checked
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 00
  • ✓ accepts 01
  • ✓ accepts 011
  • ✓ accepts 000
  • ✓ rejects ε
  • ✓ rejects 10
  • ✓ rejects 11
  • ✓ rejects 010
Tabulate and -closures
State
Compute for every state
  • For state :
  • For state :
  • For state :
  • For state :
  • For state :
Draw the resulting NFA

Since only contains , the final state of the NFA remains :

Worked Out Example 2.13 — Convert ε-NFA to NFA (Remove ε-Transitions)NFA
Worked Out Example 2.13 — Convert ε-NFA to NFA (Remove ε-Transitions) 0 0 0 0 0, 1 0 1 1 0 A B C D E
State01
→A{A, B, C, D, E}{E}
B{C}{E}
C∅{B}
D{E}∅
*E∅∅
  • Machine-checked
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 00
  • ✓ accepts 01
  • ✓ accepts 011
  • ✓ accepts 000
  • ✓ rejects ε
  • ✓ rejects 10
  • ✓ rejects 11
  • ✓ rejects 010
Answer:

, , , , , , and all other entries are .


Solutions to Important Questions (Questions 13–23, Book pp. 107–122)

Example

Important Question 13 — NDFA for Strings Containing 'aa' or 'bb' [2073 Chaitra]

Design an NDFA that accepts .

Split into two parallel branches via -transitions

From start state , branch via to (which searches for aa and accepts at ) and to (which searches for bb and accepts at ). Thus , , and :

StateSymbol Symbol Symbol
Important Question 13 — NDFA for Strings Containing 'aa' or 'bb' [2073 Chaitra]ε-NFA
Important Question 13 — NDFA for Strings Containing 'aa' or 'bb' [2073 Chaitra] a, b a a, b b ε ε a b a b a b q0 q1 q2 q3 q4 q5 q6
Statebaε
→q0∅∅{q1, q2}
q1{q1}{q3}∅
q2{q5}{q2}∅
q3{q1}{q4}∅
*q4{q4}{q4}∅
q5{q6}{q2}∅
*q6{q6}{q6}∅
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts aaabab
  • ✓ accepts babb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects aba
  • ✓ rejects baba
Trace on 'aaabab'

Following the upper branch :

Answer:

.

Example

Important Question 14 — Subset Construction on 3-State NDFA (A, B, C) [2082 Baishakh]

Convert the following NDFA into a DFA using the subset-construction method:

Important Question 14 — Subset Construction on 3-State NDFA (A, B, C) [2082 Baishakh]NFA
Important Question 14 — Subset Construction on 3-State NDFA (A, B, C) [2082 Baishakh] 0 1 0 0 1 1 A B C
State01
→A{A, B}{C}
B∅{B, C}
*C{C}∅
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 011
  • ✓ accepts 010
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 101
Write the NDFA transition table
Compute reachable subset states from
  • , .
  • , .
  • , .
  • , .
(A)
(AB)
(BC)
(C)
(phi)
Draw the equivalent DFA
Important Question 14 — Subset Construction on 3-State NDFA (A, B, C) [2082 Baishakh]DFA
Important Question 14 — Subset Construction on 3-State NDFA (A, B, C) [2082 Baishakh] 0, 1 0 1 0 0 1 1 0 1 A AB C BC phi
State01
→AABC
ABABBC
*CCphi
*BCCBC
phiphiphi
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 011
  • ✓ accepts 010
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 101
Answer:

Reachable DFA states are , , , , and , with accepting states and .

Example

Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra]

Find the equivalent DFA of the following NFA:

Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra]NFA
Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra] 0 0 1 1 0, 1 0 0, 1 q0 q1 q2
State01
→q0{q0}{q1, q2}
q1{q1, q2}{q2}
*q2{q0, q1}{q1}
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 11
  • ✓ accepts 0100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 000
Tabulate NFA transitions and expand subsets

Starting from :

  • , (new).
  • (new), .
  • , .
DFA transition table and state diagram

Denoting q0 , q12 , and q012 :

(q0)
(q12)
(q012)
Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra]DFA
Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra] 0 1 0 1 0 1 q0 q12 q012
State01
→q0q0q12
*q12q012q12
*q012q012q12
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 11
  • ✓ accepts 0100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 000
Answer:

The equivalent DFA has 3 reachable states , , and , with accepting states and .

Example

Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra]

Convert the given NFA into an equivalent DFA:

Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra]NFA
Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra] 0, 1 0, 1 0 1 0 1 A B C
State01
→A{A}{B}
B{B, C}{B}
*C{C}{B, C}
  • Machine-checked
  • ✓ accepts 10
  • ✓ accepts 010
  • ✓ accepts 110
  • ✓ accepts 101
  • ✓ accepts 100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 011
Tabulate NFA transitions and expand subsets

Starting from :

  • , (new).
  • (new), .
  • , .
DFA transition table and state diagram

With A , B , and BC :

(A)
(B)
(BC)
Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra]DFA
Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra] 0, 1 1 0 1 0 A B BC
State01
→AAB
BBCB
*BCBCBC
  • Machine-checked
  • ✓ accepts 10
  • ✓ accepts 010
  • ✓ accepts 110
  • ✓ accepts 101
  • ✓ accepts 100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 011
Answer:

The equivalent DFA has states , , and with accepting state .

Example

Important Question 17 — Convert NDFA to DFA [2074 Ashwin]

Convert the following NDFA to its equivalent DFA:

Important Question 17 — Convert NDFA to DFA [2074 Ashwin]NFA
Important Question 17 — Convert NDFA to DFA [2074 Ashwin] 1 0 0 1 0 1 1 q0 q1 q2
State01
→q0{q0, q1}{q2}
q1{q0}{q1}
*q2∅{q0, q1}
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 001
  • ✓ accepts 1101
  • ✓ accepts 0101
  • ✓ accepts 01
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 10
  • ✓ rejects 11
Tabulate NFA transitions and expand subsets

Computing DFA transitions from :

  • (new), (new).
  • , (new).
  • , .
  • , .
DFA transition table and state diagram

Let q0 , q01 , q2 , q12 , and phi :

(q0)
(q01)
(q2)
(q12)
Important Question 17 — Convert NDFA to DFA [2074 Ashwin]DFA
Important Question 17 — Convert NDFA to DFA [2074 Ashwin] 0, 1 0 0 1 1 0 1 0 1 q0 q01 q2 q12 phi
State01
→q0q01q2
q01q01q12
*q2phiq01
*q12q0q01
phiphiphi
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 001
  • ✓ accepts 1101
  • ✓ accepts 0101
  • ✓ accepts 01
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 10
  • ✓ rejects 11
Answer:

The equivalent DFA has states with accepting states and .

Example

Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik]

Convert the following non-deterministic finite automaton to a deterministic finite automaton:

Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik]NFA
Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik] 0 0 0 1 1 1 q0 q1 q2 q3 q4
State01
→q0{q1, q2, q3}∅
q1∅{q0}
q2∅{q1}
q3∅{q4}
*q4∅∅
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 0101
  • ✓ accepts 01101
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 10
  • ✓ rejects 011
Tabulate NFA transitions and expand subsets

Starting from :

  • (new), .
  • , (new).
  • , .
DFA transition table and state diagram

Let q0 , q123 , q014 , and phi :

(q0)
(q123)
(q014)
Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik]DFA
Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik] 0, 1 0 1 0 1 0 1 q0 q123 phi q014
State01
→q0q123phi
q123phiq014
phiphiphi
*q014q123q0
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 0101
  • ✓ accepts 01101
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 10
  • ✓ rejects 011
Answer:

The equivalent DFA has states , , , and , with sole accepting state .

Example

Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh]

Convert the following -NFA into an equivalent DFA:

Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh]ε-NFA
Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh] b a, b a, ε a, ε a, b b q0 q1 q2 q3
Stateabε
→q0{q0, q1}{q0}{q1}
q1{q2}{q1}{q2}
*q2{q3}{q3}∅
q3∅{q2}∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts aba
Compute the start state and its transitions

Because , the initial DFA state is

Evaluating on :

Evaluating on :

DFA transition table and state diagram

Both (q012) and (q0123) contain and accept all strings over :

(q012)
(q0123)
Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh]DFA
Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh] a, b a, b q012 q0123
Stateab
→*q012q0123q0123
*q0123q0123q0123
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts aba
Answer:

Both reachable subset states and are accepting (and merge into a single-state DFA accepting ).

Example

Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik]

Convert the following -NFA into an equivalent DFA:

Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik]ε-NFA
Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik] a, b a a, b ε b ε a a, b, ε a, ε q0 q1 q3 q2
Stateabε
→q0{q0}{q0, q3}{q1}
q1{q1, q3}∅{q2}
q3{q2}∅{q2}
*q2{q2, q3}{q2, q3}{q3}
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
Compute and transitions

Since , the initial state of the DFA is

Then

DFA transition table and state diagram
(q0123)
Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik]DFA
Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik] a, b q0123
Stateab
→*q0123q0123q0123
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ab
  • ✓ accepts ba
Answer:

The equivalent DFA consists of the single accepting state looping to itself on both and .

Example

Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin]

Convert the following NDFA (-NFA) to a DFA:

Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin]ε-NFA
Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin] a a ε b b a q0 q2 q1 q3
Stateabε
→q0{q2}∅{q1}
*q2∅∅∅
q1∅{q2, q3}∅
q3{q2, q3}∅∅
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ba
  • ✓ accepts baa
  • ✓ accepts baaa
  • ✓ rejects ε
  • ✓ rejects aa
  • ✓ rejects ab
  • ✓ rejects bb
  • ✓ rejects bab
Compute the start state and subset transitions

Since and no other -transitions exist, is the start state of the DFA:

For (which has no outgoing arrows):

For (where and ):

DFA transition table and state diagram

Denoting q01 , q2 , q23 , and phi :

State
(q01)
(q2)
(q23)
(phi)
Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin]DFA
Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin] a, b a a b a, b b q01 q2 q23 phi
Stateab
→q01q2q23
*q2phiphi
*q23q23phi
phiphiphi
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts b
  • ✓ accepts ba
  • ✓ accepts baa
  • ✓ accepts baaa
  • ✓ rejects ε
  • ✓ rejects aa
  • ✓ rejects ab
  • ✓ rejects bb
  • ✓ rejects bab
Answer:

The equivalent DFA has start state , accepting states and , and dead state (accepting ).

Example

Important Question 22 — Convert 3-State ε-NFA (q1, q2, q3) to DFA (Book pp. 118–120)

Convert the 3-state -NFA with start state , accepting state , , , , and into its equivalent DFA (as tabulated on book page 120):

Important Question 22 — Convert 3-State ε-NFA (q1, q2, q3) to DFA (Book pp. 118–120)ε-NFA
Important Question 22 — Convert 3-State ε-NFA (q1, q2, q3) to DFA (Book pp. 118–120) b ε a a b q1 q2 q3
Stateabε
→q1{q3}∅{q2}
*q2{q1}∅∅
q3∅{q2, q3}∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts aa
  • ✓ accepts ab
  • ✓ accepts abb
  • ✓ accepts aba
  • ✓ accepts aab
  • ✓ accepts abbba
  • ✓ rejects b
  • ✓ rejects bb
  • ✓ rejects ba
Evaluate subset transitions from start state
  • ,
  • ,
  • ,
  • ,
  • ,
  • .
DFA transition table and state diagram (Book p. 120)

With q12 , q123 , q23 , and phi :

(q12)
(q123)
(q23)
Important Question 22 — Convert 3-State ε-NFA (q1, q2, q3) to DFA (Book pp. 118–120)DFA
Important Question 22 — Convert 3-State ε-NFA (q1, q2, q3) to DFA (Book pp. 118–120) a, b b a a b b a q12 q123 phi q23
Stateab
→*q12q123phi
*q123q123q23
phiphiphi
*q23q12q23
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts a
  • ✓ accepts aa
  • ✓ accepts ab
  • ✓ accepts abb
  • ✓ accepts aba
  • ✓ accepts aab
  • ✓ accepts abbba
  • ✓ rejects b
  • ✓ rejects bb
  • ✓ rejects ba
Answer:

The equivalent DFA has accepting states , , and and dead state .

Example

Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra]

Remove -transitions from the given -NFA:

Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra]ε-NFA
Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra] 0, 1 1 0 ε ε A B C
State01ε
→A{A}∅{B}
B∅{B}{C}
*C{C}{C}∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 010
Tabulate the -NFA and -closures
Compute
  • For :
  • For :
  • For :
Determine final states and draw the resulting NFA

Every state whose -closure contains becomes a final state of the NFA; since , we have :

Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra]NFA
Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra] 0, 1 1 0 0, 1 0, 1 0, 1 A B C
State01
→*A{A, B, C}{B, C}
*B{C}{B, C}
*C{C}{C}
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 10
  • ✓ accepts 010
Answer:

The -free NFA has start state , final states , and transitions , , , , .


Exercises

Exercises

Question 1

Differentiate between DFA and NFA. [2082 Kartik]

Comparison between DFA and NFA: The following table details the key architectural and theoretical differences:

FeatureDeterministic Finite Automaton (DFA)Non-deterministic Finite Automaton (NFA)
Transition Function (or )
Next State UniquenessExactly one next state for every state and symbolZero, one, or multiple next states possible
(Empty) TransitionsStrictly prohibitedAllowed in -NFA without consuming input
Acceptance ConditionThe single unique computation path ends in At least one computational branch ends in
Construction DifficultyHarder; must specify every transition and trap stateEasier, intuitive, and modular to construct
State EconomyMay require up to states for an -state NFAOften exponentially more compact ( states)
Execution SpeedFast direct deterministic simulationRequires parallel branch tracking or backtracking

Computation branches and acceptance:

  • In a DFA, reading string traces a single deterministic path:

The string is accepted if and only if .

  • In an NFA, processing generates a computation tree of parallel branches. A string is accepted if at least one leaf of this tree reaches an accepting state in after consuming all of , regardless of how many other branches die or reject.

Concrete illustrative NFA (strings ending in 01):

NFA for Strings Ending in 01NFA
NFA for Strings Ending in 01 0, 1 0 1 q0 q1 q2
State01
→q0{q0, q1}{q0}
q1∅{q2}
*q2∅∅
  • Machine-checked
  • ✓ accepts 01
  • ✓ accepts 001
  • ✓ accepts 101
  • ✓ accepts 1101
  • ✓ accepts 0101
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 10
  • ✓ rejects 00
  • ✓ rejects 010

In state on symbol 0, the NFA can non-deterministically guess whether to stay in or move to to begin matching the suffix 01.

Answer:

In a DFA, assigns exactly one next state to every state-symbol pair and -moves are forbidden. In an NFA, allows zero, one, or multiple next states for a state-symbol pair (plus optional -transitions in an -NFA), and a string is accepted if at least one computation path ends in a final state.

Question 2

Give formal definition of NDFA. [2082 Baishakh, 2079 Baishakh]

Formal 5-tuple definition: A Non-deterministic Finite Automaton (NDFA / NFA) is a 5-tuple:

where:

  1. is a non-empty, finite set of states.
  2. is a non-empty, finite set of input symbols (alphabet).
  3. is the transition relation, or equivalently:

where is the power set of .

  1. is the designated start state.
  2. is the set of final (accepting) states.

Transition mechanism and language acceptance: For state and symbol , is a set of next states:

  • If , the computation branch crashes on symbol .
  • If , the automaton splits into multiple independent branches.

The extended transition function is defined inductively:

The language accepted by is:

Concrete illustrative NFA: Consider an NFA over accepting strings containing substring aa:

NFA for Substring aaNFA
NFA for Substring aa a, b a, b a a q0 q1 q2
Stateab
→q0{q0, q1}{q0}
q1{q2}∅
*q2{q2}{q2}
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts baa
  • ✓ accepts aab
  • ✓ accepts baab
  • ✓ accepts baaa
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects aba

Here, and , demonstrating non-deterministic choice on input a.

Answer:

A non-deterministic finite automaton (NDFA) is a 5-tuple where is a finite set of states, is a finite input alphabet, is the initial state, is the set of final states, and (or ) is the transition relation.

Question 3

Give a formal definition of ε-NFA. [2081 Bhadra, 2078 Kartik]

Formal 5-tuple definition: An -NFA (Non-deterministic Finite Automaton with -transitions) is formally defined as a 5-tuple:

where:

  1. is a finite set of states.
  2. is a finite alphabet ().
  3. is the transition function allowing spontaneous transitions on the empty string :
  1. is the start state.
  2. is the set of accepting states.

-closure (): The -closure of a state , denoted , is the set of all states reachable from using only -transitions (including itself):

  1. Basis: .
  2. Induction: If and , then .

For any subset :

The extended transition function satisfies:

A string is accepted if .

Concrete illustrative -NFA: Consider an -NFA for the language :

eps-NFA for 0* 1* 2*ε-NFA
eps-NFA for 0* 1* 2* 2 1 0 ε ε q0 q1 q2
State012ε
→q0{q0}∅∅{q1}
q1∅{q1}∅{q2}
*q2∅∅{q2}∅
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts 0
  • ✓ accepts 1
  • ✓ accepts 2
  • ✓ accepts 01
  • ✓ accepts 012
  • ✓ accepts 001122
  • ✓ rejects 10
  • ✓ rejects 21
  • ✓ rejects 20
  • ✓ rejects 021
  • ✓ rejects 120

Here ; because , the empty string is accepted immediately.

Answer:

An -NFA is a 5-tuple where is a finite set of states, is a finite input alphabet, is the start state, is the set of accepting states, and is the transition function allowing state transitions on the empty string without consuming input.

Question 4

Why is NDFA important although it is equivalent to a DFA? [2079 Bhadra]

Theoretical equivalence vs practical significance: By the Rabin-Scott Subset Construction theorem, any NFA can be converted into an equivalent DFA recognizing the exact same language (). However, NDFAs play an irreplaceable role in computation and compiler engineering:

Four reasons why NDFAs are essential:

  1. Exponential Succinctness: An NFA with states can describe languages that require up to states in any equivalent minimal DFA. For the language where the -th symbol from the end is 1, an NFA needs only states, whereas every equivalent DFA must possess at least states.
  2. Direct Conversion from Regular Expressions: Thompson's Construction converts any regular expression of length into an equivalent -NFA in linear time with at most states and transitions. Attempting to directly construct a DFA from a regular expression is computationally intractable in general.
  3. Simplicity in Proving Closure Properties: Operations like union, concatenation, Kleene closure, and reversal are trivial to define and prove on NFAs by linking components with -transitions, avoiding complex product constructions.
  4. Foundation for Pattern Matching & Lexing: Modern regular expression engines (e.g. grep, lexical analyzers) construct an NFA representation and simulate active states on the fly without ever materializing the exponential DFA state table.

Concrete example of succinctness: Consider an NFA recognizing strings where the second symbol from the end is 1:

NFA for Second Symbol from End is 1NFA
NFA for Second Symbol from End is 1 0, 1 1 0, 1 q0 q1 q2
State01
→q0{q0}{q0, q1}
q1{q2}{q2}
*q2∅∅
  • Machine-checked
  • ✓ accepts 10
  • ✓ accepts 11
  • ✓ accepts 010
  • ✓ accepts 111
  • ✓ accepts 0011
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 01
  • ✓ rejects 00
  • ✓ rejects 101

This compact NFA requires only states, whereas its equivalent DFA requires states. For , the NFA needs states while the DFA needs states.

Answer:

Although every NDFA has an equivalent DFA, an -state NDFA can be exponentially more succinct than its equivalent DFA (which may require up to states), and NDFAs are much easier and more natural to construct modularly from regular expressions, pattern-matching rules, and closure operations.

Past exam questions for Theory of Computation

← Finite State Machines & DFA DesignRegular Expressions & Equivalence with Finite Automata →