Question

Consider the following language: \[ L = \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} \] Which one of the following deterministic finite automata accepts \(L\)? 

• A. A
• B. B
• C. C
• D. D

Hint:

For languages of the form "strings ending with a fixed substring", design the DFA to track progressive suffix matches and ensure that the accepting state has no transitions that allow unrelated suffixes.

Answer 1

The Correct Option is D

Step 1: Interpret the language definition.
The language L consists of all binary strings whose last three symbols are exactly 011.

Therefore, a string should be accepted if and only if it finishes with the sequence 0 → 1 → 1. Any additional symbol after forming 011 must invalidate acceptance unless the suffix 011 is formed again at the very end.

---

Step 2: Determine the DFA requirements.
A DFA recognizing this language must:

• Remember partial progress toward matching the suffix 011
• Handle overlaps correctly (e.g., in strings like 0011)
• Accept only if the computation ends exactly after reading 011

This naturally leads to a four-state construction:

• Start state: no relevant suffix matched
• State after reading 0
• State after reading 01
• Accepting state after reading 011

---

Step 3: Analyze the given options.

Option (A): Fails to strictly enforce the “ends with 011” condition, as it allows acceptance even when extra symbols follow incorrectly.

Option (B): The accepting state has self-loops on both 0 and 1, which causes strings not ending in 011 to be accepted.

Option (C): Contains incorrect transitions that allow acceptance of strings whose suffix is not exactly 011.

Option (D): Correctly tracks the sequence 0 → 01 → 011 and ensures that acceptance occurs only if the input terminates in the accepting state. It also properly handles overlapping suffixes.

---

Final Conclusion:
The correct DFA that accepts exactly the set of binary strings ending with 011 is option (D).