NFA to DFA conversion — subset construction: Question bank

Reminders you'll lean on (all built in the parent):

A DFA state is a set of NFA states — the "cloud" the NFA could be in.
$ECLOSE (S)$ = everywhere you can silently drift on $ε$ -edges from $S$ (includes $S$ ).
$MOVE (S, a) = ⋃_{q \in S} δ_{N} (q, a)$ = real one-symbol step, no $ε$ yet.
$δ_{D} (S, a) = ECLOSE (MOVE (S, a))$ ; accept iff $S \cap F \neq = \emptyset$ .

True or false — justify

Every DFA produced by subset construction has exactly

2^{n}

states for an

n

-state NFA.

False.

2^{n}

is only the upper bound (all possible subsets); we build only the subsets reachable from the start, which is usually far fewer.

The subset construction can turn an NFA into a DFA that accepts a different language.

False. The whole point is

L (D) = L (N)

; the construction is a proof that NFA and DFA have equal power, both recognising exactly the regular languages (Closure Properties of Regular Languages).

If the NFA has no

ε

-transitions, then

ECLOSE (S) = S

for every set

S

True.

ECLOSE

only follows

ε

-edges; with none present nothing drifts, so each set is its own closure and the recipe collapses to

δ_{D} (S, a) = MOVE (S, a)

The resulting DFA is always the smallest DFA for that language.

False. Subset construction gives a correct DFA, often with redundant states; you still need DFA Minimization — Myhill–Nerode to get the minimal one.

A single NFA final state can make many different DFA states accepting.

True. Every subset that contains that final state (

S \cap F \neq = \emptyset

) is accepting, and one final state can appear in many reachable subsets.

The dead state

\emptyset

has an outgoing edge on every symbol, all pointing to itself.

True.

MOVE (\emptyset, a) = \emptyset

for any

a

, so once the cloud is empty it stays empty forever — a self-looping, non-accepting trap.

If a DFA state

S

satisfies

S = F

exactly, it is accepting; otherwise it is not.

False. The rule is intersection, not equality:

S

is accepting whenever

S \cap F \neq = \emptyset

, so

S

can be accepting while containing many non-final states too.

Subset construction can fail to terminate if the NFA has cycles.

False. There are at most

2^{n}

subsets total, so only finitely many DFA states can ever be created; cycles in the NFA never create infinitely many subsets.

The start state of the DFA is always

{q_{0}}

False. It is

ECLOSE ({q_{0}})

; if

q_{0}

has

ε

-edges the start cloud is larger than

{q_{0}}

Two different NFAs can produce the very same DFA under subset construction.

True. As long as they recognise the same language and drift to the same reachable clouds, the reachable-subset DFA can coincide — the construction depends on behaviour, not on how the NFA was drawn.

Spot the error

A student writes the start state as

ECLOSE (q_{0})

and calls it done — what's wrong before we even look at closures?

ECLOSE

takes a set, not a bare state; it must be

ECLOSE ({q_{0}})

. A DFA state is a set of NFA states, so the argument must be a set too.

"Each step I apply

ECLOSE

first, then

MOVE

MOVE (ECLOSE (S), a)

." Where's the bug?

The order is backwards for the result. Correct is

ECLOSE (MOVE (S, a))

: you must close after the move so any

ε

-drift following the new symbol is captured. (Closing before also matters, but the final closure after MOVE is the one people drop.)

"I generated all

2^{n}

subsets first, then drew edges." Why is this wasteful and sometimes misleading?

Most of those subsets are unreachable from the start and clutter the diagram; you only ever need the ones the start state can actually reach by following transitions.

B \cap F = {q_{1}}

, and since

q_{1}

is only one state,

B

is only partly accepting." Fix the reasoning.

There is no "partly accepting" — a DFA state is accepting or not. Because

B \cap F \neq = \emptyset

B

is fully accepting; the NFA succeeds if any single path reaches a final state.

"MOVE gave me

\emptyset

on symbol

b

, so I just leave that transition blank." Why is that not a legal DFA?

A DFA's

δ_{D}

must be total — defined on every (state, symbol) pair. The blank must go to the dead state

\emptyset

, which then self-loops and rejects.

q_{0}

is a final NFA state, so I make every reachable subset accepting." Spot the overreach.

A subset is accepting only if it contains a final state. If

q_{0} \in F

then only subsets containing

q_{0}

(and any other subset touching

F

) are accepting — not automatically all of them.

Why questions

Why must we close along

ε

-edges before reading any input, i.e. why not start at plain

{q_{0}}

The NFA can silently slide along

ε

-edges without consuming a symbol, so before the first real symbol it may already sit in several states — the DFA must carry that whole cloud from the start.

Why is "the NFA accepts if any path accepts" mirrored by "

S \cap F \neq = \emptyset

" rather than "

S \subseteq F

The NFA explores paths in parallel and only needs one successful branch. The subset

S

lists all currently-alive branches, so a single alive final state (

S \cap F \neq = \emptyset

) means acceptance; requiring

S \subseteq F

would wrongly demand all branches be final.

Why does the construction always terminate even when the NFA loops forever on some input?

The DFA states are subsets of the finite set

Q

, and there are only

2^{∣ Q ∣}

subsets. New DFA states can only be created finitely often, so the algorithm halts regardless of NFA cycles.

Why is the empty set treated as a real state rather than "no state"?

A DFA is never allowed to have no current state — it must always be somewhere.

\emptyset

encodes "all NFA branches died", which is a legitimate, permanent rejecting situation, so it becomes the trap state.

Why can

MOVE

produce a set that is not closed, forcing a follow-up

ECLOSE

MOVE

only takes real labelled steps and stops the instant the symbol is consumed; the states it lands on may themselves have outgoing

ε

-edges, so we must close again to include that fresh drift.

Why do subset construction and Thompson's construction pair up so naturally?

Regular Expressions to NFA — Thompson's construction produces

ε

-NFAs from regexes; subset construction (with

ECLOSE

) then converts those

ε

-NFAs to DFAs, completing the pipeline regex

\to

NFA

\to

DFA.

Why does the DFA sometimes have fewer states than the NFA, not just more?

Subset construction bounds states by

2^{n}

but only builds reachable clouds; if many NFA states always travel together, they collapse into a handful of subsets, so the reachable DFA can be smaller than

n

Edge cases

An NFA whose start state

q_{0}

is also a final state, with no input read. Does the DFA accept the empty string

ε

Yes. The start DFA state is

ECLOSE ({q_{0}})

, which contains

q_{0} \in F

, so it satisfies

S \cap F \neq = \emptyset

and accepts

ε

immediately.

An NFA state with no outgoing edge on symbol

a

. What is its contribution to

MOVE (S, a)

It contributes

\emptyset

(the empty union term). If every state in

S

lacks an

a

-edge,

MOVE (S, a) = \emptyset

and the DFA goes to the dead state on

a

A one-state NFA with a single state that is both start and final and self-loops on every symbol. What DFA results?

A one-state DFA equal to

{q_{0}}

, accepting, self-looping on all symbols — it accepts

Σ^{*}

, matching the NFA.

ε

-cycle in the NFA (

q ε r ε q

). Does

ECLOSE

loop forever?

No.

ECLOSE

collects a set; once

q

and

r

are already in it, revisiting adds nothing, so the fixpoint is reached and the closure is just

{q, r, \dots}

An NFA where the start state can reach a final state using only

ε

-edges. Is the empty string accepted?

Yes.

ECLOSE ({q_{0}})

then contains that final state, so the DFA start state is accepting and

ε \in L

— no symbol needs to be read.

What DFA does subset construction give for an NFA with no final states at all?

Every reachable subset has empty intersection with

F = \emptyset

, so no DFA state is accepting; the DFA recognises the empty language

\emptyset

, matching the NFA (which can never accept). Note: this is the empty language, distinct from the string set — relevant when checking with the Pumping Lemma for Regular Languages.

Can a reachable non-start subset ever be the empty set

\emptyset

while the start subset is non-empty?

Yes. If from a live cloud some symbol has no available edges,

ECLOSE (MOVE (S, a)) = \emptyset

, so the reachable DFA legitimately includes the dead state as a genuine, reachable node.