The GATE Grind

GATE 2021 CS – Question 48

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

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$?

  1. Four-state chain start -0-> q1 -1-> q2 -1-> q3(accepting), with q3 looping on 1 and returning to q1 on 0, q2 on 0 returning to q1 (figure A)
  2. Four-state chain where the accepting state loops on 0,1 (figure B)
  3. Four-state chain where the accepting state loops on 1 back to q2-type state (figure C)
  4. Four-state chain where the accepting state goes on 1 back to the start state and on 0 to q1 (figure D)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Four-state chain where the accepting state goes on 1 back to the start state and on 0 to q1 (figure D)

Explanation

After reading 011 the DFA is in the accepting state. A further 1 makes the suffix 111, which has no useful prefix of 011, so it returns to the start state. A further 0 goes to the '0' state. Only D does this correctly.