An NFA has 5 states. After applying the subset construction to convert it to an equivalent DFA, the resulting DFA has at most how many states?
A5 states — the DFA must have the same number of states as the NFA
B10 states — the construction doubles the states because each NFA transition becomes two DFA transitions
C25 states — the DFA has n² states where n is the number of NFA states
D32 states — the DFA may need one state for each subset of the NFA's 5 states
The subset construction creates one DFA state for each possible subset of NFA states. With n NFA states, there are 2^n possible subsets (the power set), so the DFA has at most 2^n states. For n = 5, that is 2^5 = 32. Many subset-states may be unreachable from the start state and can be discarded, so the actual DFA is often smaller — but 32 is the worst-case upper bound. This exponential blowup is real and can be exhibited on carefully constructed examples, but it only affects the number of states, not what languages are recognizable.
Question 2 Multiple Choice
A designer builds a 6-state NFA to recognize binary strings whose fifth-from-last character is 1. Her colleague claims this language requires a DFA with many more states and that the NFA is therefore more expressive. Which statement best corrects this claim?
AThe colleague is right — NFAs can recognize some languages that no DFA can recognize
BThe NFA and DFA recognize exactly the same language; the subset construction always produces an equivalent DFA, though it may have up to 2^n states
CThe DFA is actually more expressive — it can recognize more strings because it never gets stuck in undefined transitions
DNFAs and DFAs have equal power only for finite languages; for infinite languages like this one, NFAs are more expressive
The subset construction theorem proves that for every NFA there is a DFA accepting exactly the same strings. This holds for all regular languages, including infinite ones. For 'fifth-from-last character is 1,' the NFA has 6 states while the equivalent DFA has 32 states — but both accept the same language. Nondeterminism is a design convenience for finite automata, not a power boost. This is in sharp contrast to nondeterminism in Turing machines, where nondeterministic TMs may solve problems (in NP) that deterministic TMs cannot solve efficiently.
Question 3 True / False
An NFA accepts an input string if there exists at least one computation path — including any epsilon-transitions taken — that leads from the start state to an accepting state after consuming all input symbols.
TTrue
FFalse
Answer: True
This is the formal definition of NFA acceptance. The NFA explores all possible computation paths simultaneously (or equivalently via parallel cloning), and accepts if any one path succeeds. This 'existential' acceptance condition contrasts with the DFA, where there is exactly one computation path per input. Epsilon-transitions are free moves consuming no input; their effect is captured by the epsilon-closure operation in the subset construction. The NFA rejects only if every possible path fails to reach an accept state.
Question 4 True / False
Because NFAs can take epsilon-transitions and have multiple transitions on the same symbol, they can recognize languages that no DFA can recognize — making NFAs strictly more expressive than DFAs.
TTrue
FFalse
Answer: False
This is the key misconception the topic corrects. Despite their additional flexibility, NFAs recognize exactly the same class of languages as DFAs: the regular languages. The subset construction proves this by converting any NFA into an equivalent DFA with possible exponential state blowup. This is fundamentally different from higher-level models: nondeterministic Turing machines may solve problems in NP that deterministic TMs cannot solve efficiently. Finite automata are the clean counterexample where nondeterminism is purely a syntactic convenience — it makes some machines easier to design but cannot recognize any additional languages.
Question 5 Short Answer
Explain why NFAs and DFAs recognize exactly the same class of languages, despite NFAs appearing to have more flexibility.
Think about your answer, then reveal below.
Model answer: The subset construction converts any NFA into an equivalent DFA. The key idea: instead of tracking which single state the machine is in, track which *set* of NFA states it could be in after reading the input so far. Each set of NFA states becomes one DFA state; the DFA's transition function applies the NFA's transitions to every state in the current set and takes the union of resulting states (plus epsilon-closures). A DFA set-state is accepting if and only if it contains at least one NFA accept state. This construction is always finite (at most 2^n DFA states for n NFA states), so the equivalent DFA always exists. Since every DFA is trivially an NFA, the two models recognize exactly the same languages.
The subset construction works because nondeterminism for finite automata is equivalent to determinism with extra memory — specifically, remembering which subset of states you could currently be in. Finite automata are so restricted that this extra memory can always be pre-computed and baked into the DFA's state set. In more powerful models (pushdown automata, Turing machines), this trick fails because the 'memory' required grows unboundedly, making general deterministic simulation impossible. Finite automata are the special case where the simulation is always finite and exact.