Q1Theory of Computation
Question
4 marks
Construct a DFA that accepts strings over {0, 1} ending with '101'.
Answer
DFA for strings ending in '101'.
States: q0 (start), q1 (seen '1'), q2 (seen '10'), q3 (seen '101', final). Transitions: δ(q0,1)=q1, δ(q1,0)=q2, δ(q2,1)=q3. On failure, return to appropriate state: δ(q3,0)=q2, δ(q3,1)=q1, etc.