Consider the following language: \(L= \{ w \in \{0,1\}^* \mid w \text{ ends…
2021
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\) ?
Attempted by 254 students.
Show answer & explanation
Key idea: To recognise strings that end with 011, the DFA must remember how much of the suffix 011 has just been seen (no match, '0', or '01').
State q0 (start): no suffix of the input matches a nonempty prefix of 011. On 0 go to q1; on 1 stay in q0.
State q1: the last symbol seen is 0 (prefix of length 1). On 0 stay in q1 (still last symbol 0); on 1 go to q2 (we have seen '01').
State q2: the last two symbols seen are '01' (prefix of length 2). On 1 go to q3 (we have '011' and should accept); on 0 go back to q1 (the suffix '0' is still relevant).
State q3 (accepting): the last three symbols are '011'. On 0 move to q1 (the new last symbol is 0); on 1 move to q0 (no nonempty prefix of 011 is a suffix ending at that point).
Because the machine maintains exactly the information needed to detect the final three-symbol block '011' and updates correctly on every new input, it accepts precisely the strings that end with 011. The correct diagram is the one that implements these states and transitions.
A video solution is available for this question — log in and enroll to watch it.