Consider a language L over Σ = {a, b} L: Every string contains “aba” as…
Consider a language L over Σ = {a, b}
L: Every string contains “aba” as substring.
The number of final states in the minimal DFA of the complement of L is/are:
Answer: C. 3 — Concept Complementing a language recognized by a DFA is done by keeping the exact same states and transitions and swapping which states are accepting — every…
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 149 students.
Show answer & explanation
Correct answer: C
Concept
Complementing a language recognized by a DFA is done by keeping the exact same states and transitions and swapping which states are accepting — every state that was accepting becomes non-accepting, and every state that was non-accepting becomes accepting. If the original DFA is already minimal, the resulting automaton stays minimal too: two states are distinguishable when some string drives them to different accept/reject outcomes, and swapping every state's status at once does not remove any such difference — it only flips both sides of it together.
Applying it to this DFA
For L (strings over {a, b} that contain "aba" as a substring), the standard automaton tracks how much of the pattern "aba" has just been matched, using one state for each amount of progress — none, "a", "ab", or a completed "aba":
State | Meaning | On reading 'a' | On reading 'b' |
|---|---|---|---|
q0 | no part of "aba" matched yet (start state) | q1 | q0 |
q1 | matched "a" | q1 | q2 |
q2 | matched "ab" | q3 | q0 |
q3 | matched "aba" — a complete match has already occurred | q3 | q3 |
Once state q3 is reached, the string already contains "aba", and no later symbol can undo that, so q3 loops back to itself on both symbols. This gives a 4-state DFA for L with exactly one accepting state, q3; every other state is reachable from another by a string that q3 is not (for example, from q0 the string "ba" ends at q1, while from q1 the very same string "ba" ends at q3), so all four states are already pairwise distinguishable — this is the minimal DFA for L.
Complementing this DFA keeps the same four states and the same transition table, but swaps which states accept: q0, q1 and q2 — the three states reached while "aba" has not yet fully appeared — become the accepting states, while q3 becomes non-accepting.
Cross-check
The string "aba" itself contains "aba" as a substring, so it belongs to L and must therefore be rejected by the complement of L. Tracing "aba" through the automaton (q0 → q1 → q2 → q3) ends at q3, and since q3 is non-accepting in the complement, "aba" is correctly rejected — confirming the swapped diagram is consistent with what a complement must do. Because the same strings that distinguished the four states before the swap still distinguish them afterwards, the complement's automaton is also already minimal, so no states can be merged.
Result
The minimal DFA of the complement of L has three accepting (final) states — q0, q1 and q2.