Questions: Nondeterministic Finite Automata (NFA)

Question 1

A student argues that NFAs must be more powerful than DFAs because NFAs can branch into multiple states simultaneously while DFAs follow exactly one path. Is this claim correct?

• A. Yes — the branching ability means NFAs can recognize some non-regular languages that DFAs cannot
• B. No — every NFA can be converted to an equivalent DFA via the subset construction, so both models recognize exactly the regular languages
• C. Yes — NFAs with ε-transitions recognize a strictly larger class of languages than DFAs without ε-transitions
• D. No — DFAs are actually more powerful because their determinism guarantees a single, predictable execution path

Answer: (B)

This is the central misconception about NFAs. Despite their apparent extra freedom, NFAs are provably equivalent in expressive power to DFAs. The subset construction converts any NFA into a DFA where each DFA state represents a set of NFA states that could be simultaneously active. The resulting DFA accepts exactly the same strings. Both models recognize precisely the regular languages — nothing more, nothing less. NFAs are not more powerful; they are more *convenient*: they can be exponentially smaller than equivalent DFAs, and they are easier to construct compositionally.

Question 2

An NFA processing input string 'ab' has three computation paths: path 1 ends in a reject state, path 2 gets stuck (no valid transition exists), and path 3 ends in an accept state. What is the NFA's decision on 'ab'?

• A. Reject — a majority of paths do not reach an accept state
• B. Accept — at least one computation path ends in an accept state
• C. Reject — path 2 getting stuck counts as a definitive rejection that overrides other paths
• D. Undefined — the NFA cannot make a decision when some computation paths get stuck

Answer: (B)

NFA acceptance uses the existential quantifier: a string is accepted if *at least one* computation path ends in an accept state when all input has been consumed. A stuck path (no valid transition) is simply a dead path — it contributes nothing, neither accept nor reject. A rejecting path similarly is just one branch that didn't work. The nondeterminism is like searching a maze by cloning yourself at every fork: you succeed if *any* clone reaches the exit, regardless of what happens to the others. The all-paths-must-accept semantics would give a very different (and weaker) computational model.

Question 3

An NFA accepts a string primarily if MOST possible computation paths on that string end in accept states.

• T. True
• F. False

Answer: False

The NFA acceptance condition is existential, not universal: a string is accepted if *at least one* computation path ends in an accept state. This is a foundational definition that distinguishes NFAs from their 'dual' — a model requiring all paths to accept, which would be far less useful. The existential semantics is what makes nondeterminism powerful as a mathematical abstraction: it lets you think of the NFA as 'guessing' the right path and verifying it, rather than exhaustively checking all paths.

Question 4

An NFA with n states may require a DFA with up to 2ⁿ states to simulate, because each DFA state in the subset construction must represent a possible subset of active NFA states.

• T. True
• F. False

Answer: True

The subset construction DFA has one state for every possible subset of NFA states — and there are 2ⁿ subsets of an n-element set (the power set). In the worst case, all 2ⁿ subsets are reachable and distinct in their behavior, requiring exponentially many DFA states. This exponential blowup is not merely theoretical — there exist families of NFAs for which the minimal equivalent DFA is provably exponential in size. This is the practical tradeoff: NFAs are compact and easy to build, but simulation requires potentially exponential space. For applications like regular expression engines, this tradeoff drives important implementation decisions.

Question 5

Why are NFAs more convenient than DFAs for building automata for language operations like union, even though both models are equally expressive?

Model answer: NFAs allow nondeterministic 'guessing.' To build an NFA for A ∪ B, add a new start state with ε-transitions to the start states of both existing automata — the NFA nondeterministically chooses which language to verify. With DFAs, you need a product construction that simultaneously tracks states in both machines. NFAs are compositional: the union, concatenation, and Kleene star constructions each require only a few new states and ε-transitions, making NFAs the natural intermediate representation between regular expressions and DFAs.

The same compositional advantage applies to concatenation: add an ε-transition from every accept state of the first machine to the start state of the second, letting the NFA nondeterministically 'guess' when the first part of the string ends. For Kleene star, add ε-transitions back from accept states to the start state. None of these operations require understanding the internal structure of the existing machines — they just add wiring. This is why regular expression to automaton conversion (Thompson's construction) produces NFAs, not DFAs. The resulting NFA is then converted to a DFA only when needed for execution.