The below DFA accepts the set of all strings over {0,1} that
2009
The below DFA accepts the set of all strings over {0,1} that
- A.
begin either with 0 or 1
- B.
end with 0
- C.
end with 00
- D.
contain the substring 00.
Attempted by 264 students.
Show answer & explanation
Correct answer: C
Answer: The DFA accepts exactly those strings that end with 00.
Reasoning: Label the states as follows: start state S (left), middle state M (middle), and accepting state A (right). The states track the trailing suffix of the input:
S: no trailing 0 (either the input so far is empty or the last symbol seen is 1).
M: exactly one trailing 0 (the last symbol is 0 but the last two are not 00).
A: at least two trailing zeros (the last two symbols are 00). This is the only accepting state.
Key transitions:
From S: reading 1 stays in S; reading 0 moves to M.
From M: reading 0 moves to A (producing the suffix 00); reading 1 moves back to S.
From A: reading 0 stays in A (still ends with 00); reading 1 goes to S (no trailing zeros).
Conclusion: Because the accepting state corresponds exactly to inputs whose last two symbols are 00, the language recognized by the DFA is the set of all strings over {0,1} that end with 00.