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$?
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)
Four-state chain where the accepting state loops on 0,1 (figure B)
Four-state chain where the accepting state loops on 1 back to q2-type state (figure C)
Four-state chain where the accepting state goes on 1 back to the start state and on 0 to q1 (figure D)
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.
More Regular Expressions and Finite Automata questions
GATE 2020 CS Q61– Consider the following language. L=\x\a,b\* number of a's in x is divisible by 2 but not…
GATE 2019 CS Q58– Let be the set of all bijections from \1,,5\ to \1,,5\, where id denotes the identity…
GATE 2018 CS Q16– Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is…
GATE 2018 CS Q62– Given a language L, define Li as follows: L0=\\ and Li=Li-1 L for all i>0. The order of a…
GATE 2015 CS (CS1) Q49– [Two DFAs, each with two states. DFA M: the start state loops on b, reads a to move to the…
GATE 2016 CS (CS1) Q28– Which one of the following regular expressions represents the language: the set of all…