Solution

The correct answer is: Option 4

Key Points

Goal of the question

• You are given a DFA (deterministic finite automaton) over Σ = {a, b, c}.
• You must choose which of the proposed NFAs (nondeterministic FAs) is a valid one for the same language—that is, it accepts exactly the strings accepted by the DFA.
• Remember: every DFA is already an NFA. So a candidate NFA is valid iff, after accounting for any ε-moves, it reproduces the DFA’s effect for each input symbol from each state.

How to check that an NFA is equivalent to a given DFA

1. Read the DFA diagram and write its transition function δ_DFA(q, σ) for every state q and symbol σ ∈ {a, b, c} (each pair has exactly one target because it is a DFA).
2. For a candidate NFA, compute the set of states reachable in one step on symbol σ from q, allowing an optional ε-closure before and after reading σ:
   ReachNFA(q, σ) = ε-closure( δNFA( ε-closure(q), σ ) )
   The NFA is valid iff this set is exactly { δ_DFA(q, σ) } for all pairs (q, σ).
3. ε-arcs are allowed, but they must not introduce any extra consuming transitions on a, b, or c that the DFA does not have.

Why Option 4 is valid

• Option 4 preserves all the symbol-labelled moves of the DFA (the a, b, c arrows agree with the DFA diagram).
• It adds only ε-moves from accepting states to a common “sink-accept” node (q4 in the option), which does not change which strings are accepted:
  • ε-moves do not consume input symbols.
  • Introducing an ε-path after reaching an accepting configuration keeps the string accepted but does not accept any string that was previously rejected.
• Therefore, after taking ε-closures, the set of a/b/c successors from every state is identical to the DFA’s single successor. Hence the language is unchanged.

Why the other options are not valid

• Option 1: introduces a symbol-labelled edge that the DFA does not have (one of the a/b/c arrows goes to a different node than in the DFA). This changes δ(q, σ) and hence changes the language.
• Option 2: is missing a required symbol-labelled transition present in the DFA (one DFA arrow is not reproduced), so some strings accepted by the DFA become rejected by this NFA.
• Option 3: reverses/misplaces at least one labelled transition compared with the DFA, again altering δ(q, σ) and hence the language.

Takeaway

• To build a valid NFA from a DFA, keep all the DFA’s labelled transitions exactly as they are; you may add ε-moves (e.g., to merge accepting states), but they must not create new ways to consume a symbol that were not allowed by the DFA.
• Among the provided figures, only Option 4 respects these rules, so it is the correct choice.