GATE CSE 2021 Set 1 | Question: 38

Question

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

• A.
• B.
• C.
• D.

Comments

Option D

---

ans D

---

@Deepak Poonia

any better way to solve this sum

or 

we have to find counter string (by hit and trial ??)

+ running two DFA parallel to merge them is very time consuming ??

Answer 1

The correct automata for $L$ must accept every binary string ending with “011” and not accept any other binary string.

• A. False it accepts binary strings ending with $111$
• B. False it accepts binary strings ending with $0, 00, 00,100,001,111$ etc.
• C. False it accepts binary string ending with $1111$
• D. True it accepts all strings that end with $011$ and no other strings.

Correct Ans: D

Comments

I think its option B which is correct and not option D.

---

@dpk You can either correct your thinking or get negative marks 😊

---

Just see the question once ; they are saying the DFA accepts strings ends 011 ; it means last state doesn’t have any itself function.

---

Another quick approach

Options A and B accept wrong strings even after $011$ [self-loops in final state is wrong]. Hence False.

Option C on reaching final state if receives $1$ goes to a state from which even not ending in $011$ is being accepted. Hence False. 

Thus option D is correct.

Answer 2

Correct Answer: Option D

Solution :-

Options A and B accept wrong strings even after $011$ [self-loops in final state is wrong]. Hence False.

Option C on reaching final state if receives $1$ goes to a state from which even strings which are ‘not ending in $011$’ are being accepted. Hence False. 

Thus Option D is correct.

Comments

Nice