GATE CS 2021 Set 1 Q.48 (CS Q.38): Regular Expressions, Finite Automata and Regular Languages

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

Deterministic finite automaton option A with four states where the final state has a self-loop on 1 and transition on 0 to the second state.

Option B DFA: start state (self-loop on 1) goes to the second state on 0; the second state has a self-loop on 0 and goes to the third state on 1; the third state returns to the second state on 0 and goes to the accepting state on 1; the accepting state has a self-loop on 0,1.

Deterministic finite automaton option C with four states where the final state transitions on 1 back to the third state.

Deterministic finite automaton option D with four states where the final state transitions on 1 back to the initial state and on 0 to the second state.

Official answer and solution

Official answer: D
From: Official GATE 2021 answer key

Solution

Construct the state transitions of the minimal DFA that detects the pattern 011 at the end of the input string.

The language $L$ consists of all binary strings ending in $011$ . The minimal DFA requires 4 states corresponding to the longest matched prefix of $011$ that appears as a suffix of the input read so far:

State $q_0$ (start state): suffix $\epsilon$
State $q_1$ : suffix ending in $0$
State $q_2$ : suffix ending in $01$
State $q_3$ (accept state): suffix ending in $011$

Verify the transitions:

From $q_0$ : on 0 go to $q_1$ ; on 1 stay in $q_0$ .
From $q_1$ : on 0 stay in $q_1$ (suffix is still 0); on 1 go to $q_2$ (suffix is 01).
From $q_2$ : on 0 go to $q_1$ (suffix 010 ends in 0); on 1 go to $q_3$ (suffix is 011).
From $q_3$ : on 0 go to $q_1$ (suffix 0110 ends in 0); on 1 go to $q_0$ (suffix 0111 has no overlap with 011, so it resets to $\epsilon$ ).

DFA diagram D faithfully implements these transitions with $q_3$ as the sole accepting state.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 48 of 65, printed as CS Q.38
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source