Questions: NFA to DFA Conversion (Subset Construction)

Question 1

An NFA has 5 states. After applying subset construction, the resulting DFA has 12 states. A student says this result must be wrong because the DFA should have at most 2⁵ = 32 states and they expected far fewer. Which response is most accurate?

• A. The result is wrong — 12 states is too many for a 5-state NFA; the algorithm was applied incorrectly
• B. The result is plausible — subset construction builds states on demand from reachable subsets, and 12 of the 32 possible subsets may be reachable from the initial ε-closure
• C. The result is wrong — subset construction always produces exactly n+1 states for an n-state NFA
• D. The result is wrong — the DFA should have exactly 32 states since all subsets must be represented

Answer: (B)

The subset construction algorithm only creates DFA states for subsets of NFA states that are actually reachable from the initial state. For an n-state NFA, there are 2ⁿ possible subsets, but most are typically unreachable. A 5-state NFA might produce anywhere from a handful to all 32 states depending on the NFA's structure. 12 states is completely plausible. The key insight is that the algorithm builds states lazily — only when a new subset is encountered during transition computation.

Question 2

In the subset construction, a DFA state corresponding to the set {q1, q3, q5} is an accepting state if:

• A. All of q1, q3, and q5 are accepting states in the NFA
• B. The majority (at least 2 of 3) of the NFA states in the set are accepting states
• C. At least one of q1, q3, or q5 is an accepting state in the NFA
• D. None of q1, q3, or q5 are accepting states (the DFA only accepts when the NFA has exhausted all paths)

Answer: (C)

An NFA accepts a string if *any* path through the NFA — any possible sequence of state transitions — reaches an accepting state. The DFA state {q1, q3, q5} represents 'the NFA could currently be in q1, q3, or q5.' Since the NFA accepts whenever any active path leads to an accept state, the DFA state is accepting if the set contains at least one NFA accept state. This preserves the NFA's acceptance semantics: if there's any way the NFA could be in an accepting configuration, the DFA accepts.

Question 3

A DFA produced by subset construction from an NFA recognizes exactly the same language as the original NFA.

• T. True
• F. False

Answer: True

This is the fundamental theorem that subset construction proves: NFAs and DFAs are equivalent in expressive power — they recognize exactly the same class of languages (the regular languages). The subset construction constructs a DFA that perfectly simulates the NFA by tracking all possible NFA states simultaneously. Every string accepted by the NFA will lead the DFA to a state containing at least one NFA accept state, and vice versa. This equivalence is why we can freely choose between NFA and DFA representations when designing automata.

Question 4

An NFA with n states usually requires a DFA with exactly 2ⁿ states after subset construction.

• T. True
• F. False

Answer: False

2ⁿ is the theoretical worst case, not the typical outcome. Subset construction only creates DFA states for subsets of NFA states reachable from the initial ε-closure by following actual transitions. In most practical NFAs, the vast majority of the 2ⁿ possible subsets are never encountered during the algorithm. A typical 5-state NFA might produce 8–12 DFA states rather than 32. The exponential blowup is real as a worst-case bound and can be demonstrated with specific adversarial NFA constructions, but it is not the normal result.

Question 5

Why does the subset construction algorithm prove that nondeterminism adds no expressive power over determinism for finite automata?

Model answer: The subset construction takes any NFA and produces a DFA that simulates it exactly, by treating each possible set of simultaneously active NFA states as a single DFA state. Since any NFA can be mechanically converted to an equivalent DFA, both models can recognize the same set of languages. If nondeterminism added expressive power, there would exist some language that an NFA could recognize but no DFA could — but the construction shows this is impossible. Nondeterminism in finite automata therefore only provides conciseness (NFAs can be exponentially more compact), not additional computational power.

This contrasts sharply with other computational models: for pushdown automata, nondeterminism does add expressive power (nondeterministic PDAs recognize all context-free languages; deterministic PDAs recognize only a proper subset). For Turing machines, the question of whether nondeterminism adds power is the P vs NP problem — still unresolved. The finite automaton case is one of the few where we can definitively answer that nondeterminism adds nothing but compactness.