NFA, ε-NFA & Their Equivalence with DFA
Open in the Padhaiko app2.2.2 Non-Deterministic Finite Automata (NDFA or NFA)
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:
- For a given state and input symbol , there may be several possible next states (or zero next states, in which case that computational branch halts/chokes).
- The automaton may also change state spontaneously without consuming any input symbol along an empty-string transition (-transition).
- An input string is accepted if at least one sequence of non-deterministic choices leads from the start state to some accepting state upon reading all of .
Formally, a general non-deterministic finite automaton is a 5-tuple (quintuple)
where:
- is a finite set of states,
- is a finite input alphabet,
- is the initial (start) state,
- is the set of final (accepting) states, and
- is the transition relation (equivalently written as a set-valued transition function for an NFA without -moves, or for an -NFA).
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:
| State | a | b |
|---|---|---|
| →q0 | {q0, q1} | {q0} |
| q1 | ∅ | {q2} |
| *q2 | ∅ | ∅ |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aab
- ✓ accepts bab
- ✓ accepts abab
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ba
- ✓ rejects aba
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:
- Digital Circuit Design & Verification: Software for designing and checking the behavior of sequential digital circuits and concurrent protocols.
- Compiler Lexical Analyzers: Regular expressions describing programming-language tokens are first compiled into NDFAs before subset construction builds the scanner table.
- Large-Scale Text Scanning: Searching large collections of text (such as indexing web pages or multi-pattern intrusion detection) for multiple patterns simultaneously.
- Formal Verification Systems: Model-checking software for verifying finite-state hardware and communication systems.
| Aspect | Deterministic Finite Automaton (DFA) | Non-Deterministic Finite Automaton (NFA) |
|---|---|---|
| Next-State Uniqueness | For each , there is exactly one next state . | For each , there may be zero, one, or multiple next states in . |
| Transition Signature | . | (or ). |
| Empty-String () Moves | Not allowed (-transitions cannot occur). | Allowed in an -NFA without consuming input. |
| Acceptance Condition | The unique computation path for ends in . | At least one computation path for ends in . |
| State Count & Complexity | May 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)
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.
Let with , , , and :
- loops on and until it non-deterministically guesses the start
bof eitherbborbab(moving to ). - From , reading
breaches (completingbb, which transitions via to ), while readingareaches (matchingba, which transitions onbto ).
| State | |||
|---|---|---|---|
| State | a | b | ε |
|---|---|---|---|
| →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
Eliminating the -move from to makes both and accepting trap states ():
| State | ||
|---|---|---|
| State | a | b |
|---|---|---|
| →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
(or with ).
NDFA for Regular Expression r = b*ab
Design a non-deterministic finite automaton (NDFA) for the regular expression .
Let where , , , and :
| State | ||
|---|---|---|
'bbab'| State | b | a |
|---|---|---|
| →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":
with .
DFA and NFA for Regular Expression (ab ∪ aba)*
Design a DFA (and corresponding NFA) for the regular expression .
Let with , , , and :
- : start state (, accepting).
- : read
aat the beginning of a blockaboraba. - : read
ab(accepting; readinganext moves to since thatamay either completeabaor start a new block). - : read
aba(accepting; readinganext meansabafinished and a new block started at , whereas readingbnext means the previous block wasaband we just completed anotherabat ). - : dead state.
| State | a | b |
|---|---|---|
| →*q0 | q1 | q4 |
| q1 | q4 | q2 |
| q4 | q4 | q4 |
| *q2 | q3 | q4 |
| *q3 | q1 | q2 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts ab
- ✓ accepts aba
- ✓ accepts abab
- ✓ accepts abaab
- ✓ accepts ababaab
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aa
- ✓ rejects abb
- ✓ rejects baba
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):
| State | a | b |
|---|---|---|
| →*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
The DFA has 5 states with , while the equivalent NFA requires only 3 states with .
2.3 Equivalence of DFA and NFA (Subset Construction)
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:
- Initial State of DFA: Set the start state of to the singleton subset and compute for every .
- 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.)
- 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 ).
Convert NFA to Equivalent DFA
Convert the following NFA into an equivalent DFA:
| State | b | a |
|---|---|---|
| →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
Let be the transition function of the DFA and be the transition function of the NFA. Starting from :
For :
For :
Denoting the subset states as q0 , q1 , q12 (accepting, since ), and phi :
| DFA State | ||
|---|---|---|
(q0) | ||
(q1) | ||
(q12) | ||
(phi) |
| State | b | a |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q12 | phi |
| *q12 | q12 | phi |
| phi | phi | phi |
- Machine-checked
- ✓ accepts ab
- ✓ accepts bab
- ✓ accepts abb
- ✓ accepts babb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aba
- ✓ rejects ba
The equivalent DFA has states , start state , and sole accepting state .
2.4 Conversion of ε-NFA to DFA and ε-NFA to NFA
ε-Closure and Conversion of ε-NFA
An -NFA is an NFA that permits transitions on the empty string without consuming any input symbol.
- -closure of a state : Denoted , it is the set of all states reachable from by following zero or more -transitions (so always holds). For a set of states ,
- Converting an -NFA to an equivalent DFA:
- The start state of the DFA is .
- For every DFA subset state and every input symbol ,
- Any subset state containing an accepting state of the -NFA () is an accepting state of the DFA.
- Converting an -NFA to an equivalent NFA (removing -transitions): Keep the same state set and start state , define the NFA transition function by
and mark a state as accepting in the NFA if .
Convert ε-NFA to DFA
Convert the following -NFA into an equivalent DFA:
| State | a | b | ε |
|---|---|---|---|
| →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
For :
For :
For :
Writing q012 , q12 , q2 , and phi (all three non-empty subsets contain and are accepting):
| State | ||
|---|---|---|
(q012) | ||
(q12) | ||
(q2) | ||
(phi) |
| State | a | b |
|---|---|---|
| →*q012 | q012 | q12 |
| *q12 | q2 | q12 |
| *q2 | q2 | phi |
| phi | phi | phi |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts aabba
- ✓ rejects bbab
- ✓ rejects bab
The equivalent DFA has start state and accepting states (recognizing ).
Convert 5-State ε-NFA to DFA
Convert the following -NFA into an equivalent DFA:
| State | b | a | ε |
|---|---|---|---|
| →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
Following the -edges , , , and :
- From :
- From :
- From :
- From :
Let q0123 , q01234 , q234 , q34 , and phi :
| State | ||
|---|---|---|
(q0123) | ||
(q01234) | ||
(q234) | ||
(q34) | ||
(phi) |
| State | a | b |
|---|---|---|
| →q0123 | q01234 | q234 |
| *q01234 | q01234 | q234 |
| *q234 | q34 | q34 |
| *q34 | q34 | phi |
| phi | phi | phi |
- Machine-checked
- ✓ accepts a
- ✓ accepts b
- ✓ accepts aa
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts bb
- ✓ accepts aba
- ✓ accepts abb
- ✓ rejects ε
- ✓ rejects bbba
- ✓ rejects bab
The equivalent DFA has start state and accepting states , , and .
Convert ε-NFA to NFA (Remove ε-Transitions)
Convert the following -NFA into an equivalent NFA without -transitions:
| State | 0 | 1 | ε |
|---|---|---|---|
| →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
| State | ||||
|---|---|---|---|---|
- For state :
- For state :
- For state :
- For state :
- For state :
Since only contains , the final state of the NFA remains :
| State | 0 | 1 |
|---|---|---|
| →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
, , , , , , and all other entries are .
Solutions to Important Questions (Questions 13–23, Book pp. 107–122)
Important Question 13 — NDFA for Strings Containing 'aa' or 'bb' [2073 Chaitra]
Design an NDFA that accepts .
From start state , branch via to (which searches for aa and accepts at ) and to (which searches for bb and accepts at ). Thus , , and :
| State | Symbol | Symbol | Symbol |
|---|---|---|---|
| State | b | a | ε |
|---|---|---|---|
| →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
'aaabab'Following the upper branch :
.
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:
| State | 0 | 1 |
|---|---|---|
| →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
- , .
- , .
- , .
- , .
(A) | ||
(AB) | ||
(BC) | ||
(C) | ||
(phi) |
| State | 0 | 1 |
|---|---|---|
| →A | AB | C |
| AB | AB | BC |
| *C | C | phi |
| *BC | C | BC |
| phi | phi | phi |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 011
- ✓ accepts 010
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 00
- ✓ rejects 11
- ✓ rejects 101
Reachable DFA states are , , , , and , with accepting states and .
Important Question 15 — Equivalent DFA of 3-State NFA [2080 Bhadra]
Find the equivalent DFA of the following NFA:
| State | 0 | 1 |
|---|---|---|
| →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
Starting from :
- , (new).
- (new), .
- , .
Denoting q0 , q12 , and q012 :
(q0) | ||
(q12) | ||
(q012) |
| State | 0 | 1 |
|---|---|---|
| →q0 | q0 | q12 |
| *q12 | q012 | q12 |
| *q012 | q012 | q12 |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 11
- ✓ accepts 0100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 00
- ✓ rejects 000
The equivalent DFA has 3 reachable states , , and , with accepting states and .
Important Question 16 — Convert NFA (A, B, C) to Equivalent DFA [2081 Chaitra]
Convert the given NFA into an equivalent DFA:
| State | 0 | 1 |
|---|---|---|
| →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
Starting from :
- , (new).
- (new), .
- , .
With A , B , and BC :
(A) | ||
(B) | ||
(BC) |
| State | 0 | 1 |
|---|---|---|
| →A | A | B |
| B | BC | B |
| *BC | BC | BC |
- Machine-checked
- ✓ accepts 10
- ✓ accepts 010
- ✓ accepts 110
- ✓ accepts 101
- ✓ accepts 100
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 01
- ✓ rejects 011
The equivalent DFA has states , , and with accepting state .
Important Question 17 — Convert NDFA to DFA [2074 Ashwin]
Convert the following NDFA to its equivalent DFA:
| State | 0 | 1 |
|---|---|---|
| →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
Computing DFA transitions from :
- (new), (new).
- , (new).
- , .
- , .
Let q0 , q01 , q2 , q12 , and phi :
(q0) | ||
(q01) | ||
(q2) | ||
(q12) |
| State | 0 | 1 |
|---|---|---|
| →q0 | q01 | q2 |
| q01 | q01 | q12 |
| *q2 | phi | q01 |
| *q12 | q0 | q01 |
| phi | phi | phi |
- Machine-checked
- ✓ accepts 1
- ✓ accepts 001
- ✓ accepts 1101
- ✓ accepts 0101
- ✓ accepts 01
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 10
- ✓ rejects 11
The equivalent DFA has states with accepting states and .
Important Question 18 — Convert 5-State NFA to DFA [2072 Kartik]
Convert the following non-deterministic finite automaton to a deterministic finite automaton:
| State | 0 | 1 |
|---|---|---|
| →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
Starting from :
- (new), .
- , (new).
- , .
Let q0 , q123 , q014 , and phi :
(q0) | ||
(q123) | ||
(q014) |
| State | 0 | 1 |
|---|---|---|
| →q0 | q123 | phi |
| q123 | phi | q014 |
| phi | phi | phi |
| *q014 | q123 | q0 |
- Machine-checked
- ✓ accepts 01
- ✓ accepts 0101
- ✓ accepts 01101
- ✓ rejects ε
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 00
- ✓ rejects 10
- ✓ rejects 011
The equivalent DFA has states , , , and , with sole accepting state .
Important Question 19 — Convert ε-NFA to DFA [2080 Baishakh]
Convert the following -NFA into an equivalent DFA:
| State | a | b | ε |
|---|---|---|---|
| →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
Because , the initial DFA state is
Evaluating on :
Evaluating on :
Both (q012) and (q0123) contain and accept all strings over :
(q012) | ||
(q0123) |
| State | a | b |
|---|---|---|
| →*q012 | q0123 | q0123 |
| *q0123 | q0123 | q0123 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts aba
Both reachable subset states and are accepting (and merge into a single-state DFA accepting ).
Important Question 20 — Convert 4-State ε-NFA to Equivalent DFA [2078 Kartik]
Convert the following -NFA into an equivalent DFA:
| State | a | b | ε |
|---|---|---|---|
| →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
Since , the initial state of the DFA is
Then
(q0123) |
| State | a | b |
|---|---|---|
| →*q0123 | q0123 | q0123 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ab
- ✓ accepts ba
The equivalent DFA consists of the single accepting state looping to itself on both and .
Important Question 21 — Convert ε-NFA to DFA [2076 Ashwin]
Convert the following NDFA (-NFA) to a DFA:
| State | a | b | ε |
|---|---|---|---|
| →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
Since and no other -transitions exist, is the start state of the DFA:
For (which has no outgoing arrows):
For (where and ):
Denoting q01 , q2 , q23 , and phi :
| State | ||
|---|---|---|
(q01) | ||
(q2) | ||
(q23) | ||
(phi) |
| State | a | b |
|---|---|---|
| →q01 | q2 | q23 |
| *q2 | phi | phi |
| *q23 | q23 | phi |
| phi | phi | phi |
- Machine-checked
- ✓ accepts a
- ✓ accepts b
- ✓ accepts ba
- ✓ accepts baa
- ✓ accepts baaa
- ✓ rejects ε
- ✓ rejects aa
- ✓ rejects ab
- ✓ rejects bb
- ✓ rejects bab
The equivalent DFA has start state , accepting states and , and dead state (accepting ).
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):
| State | a | b | ε |
|---|---|---|---|
| →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
- ,
- ,
- ,
- ,
- ,
- .
With q12 , q123 , q23 , and phi :
(q12) | ||
(q123) | ||
(q23) |
| State | a | b |
|---|---|---|
| →*q12 | q123 | phi |
| *q123 | q123 | q23 |
| phi | phi | phi |
| *q23 | q12 | q23 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts a
- ✓ accepts aa
- ✓ accepts ab
- ✓ accepts abb
- ✓ accepts aba
- ✓ accepts aab
- ✓ accepts abbba
- ✓ rejects b
- ✓ rejects bb
- ✓ rejects ba
The equivalent DFA has accepting states , , and and dead state .
Important Question 23 — Remove ε-Transitions from ε-NFA [2081 Bhadra]
Remove -transitions from the given -NFA:
| State | 0 | 1 | ε |
|---|---|---|---|
| →A | {A} | ∅ | {B} |
| B | ∅ | {B} | {C} |
| *C | {C} | {C} | ∅ |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 0
- ✓ accepts 1
- ✓ accepts 01
- ✓ accepts 10
- ✓ accepts 010
- For :
- For :
- For :
Every state whose -closure contains becomes a final state of the NFA; since , we have :
| State | 0 | 1 |
|---|---|---|
| →*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
The -free NFA has start state , final states , and transitions , , , , .
Exercises
Exercises
Differentiate between DFA and NFA. [2082 Kartik]
Comparison between DFA and NFA: The following table details the key architectural and theoretical differences:
| Feature | Deterministic Finite Automaton (DFA) | Non-deterministic Finite Automaton (NFA) |
|---|---|---|
| Transition Function | (or ) | |
| Next State Uniqueness | Exactly one next state for every state and symbol | Zero, one, or multiple next states possible |
| (Empty) Transitions | Strictly prohibited | Allowed in -NFA without consuming input |
| Acceptance Condition | The single unique computation path ends in | At least one computational branch ends in |
| Construction Difficulty | Harder; must specify every transition and trap state | Easier, intuitive, and modular to construct |
| State Economy | May require up to states for an -state NFA | Often exponentially more compact ( states) |
| Execution Speed | Fast direct deterministic simulation | Requires 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):
| State | 0 | 1 |
|---|---|---|
| →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.
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.
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:
- is a non-empty, finite set of states.
- is a non-empty, finite set of input symbols (alphabet).
- is the transition relation, or equivalently:
where is the power set of .
- is the designated start state.
- 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:
| State | a | b |
|---|---|---|
| →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.
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.
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:
- is a finite set of states.
- is a finite alphabet ().
- is the transition function allowing spontaneous transitions on the empty string :
- is the start state.
- 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):
- Basis: .
- 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 :
| State | 0 | 1 | 2 | ε |
|---|---|---|---|---|
| →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.
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.
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:
- 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. - 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.
- 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.
- 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:
| State | 0 | 1 |
|---|---|---|
| →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.
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.