2,547 views

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. 2. 3. 4. Option D ans D

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

1. False it accepts binary strings ending with $111$
2. False it accepts binary strings ending with $0, 00, 00,100,001,111$ etc.
3. False it accepts binary string ending with $1111$
4. True it accepts all strings that end with $011$ and no other strings.

Correct Ans: D

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.

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.

Nice