retagged by
4,175 views
15 votes
15 votes

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

retagged by

2 Answers

Best answer
13 votes
13 votes

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

selected by
3 votes
3 votes

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.

Answer:

Related questions

14 votes
14 votes
5 answers
1
6 votes
6 votes
1 answer
4
Arjun asked Feb 18, 2021
4,832 views
$$\begin{array}{|c|c|c|c|} \hline \textbf{Items} & \textbf{Cost} & \textbf{Profit %} & \textbf{Marked Price} \\ & \text{(₹)} & & \text{(₹)} \\\hline P &5,400 & -&5,86...