in Theory of Computation retagged by
2,547 views
9 votes
9 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?$

in Theory of Computation retagged by
by
2.5k views

2 Comments

Option D
2
2

ans D

0
0

2 Answers

7 votes
7 votes
Best answer

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

4 Comments

I think its option B which is correct and not option D.
0
0
@dpk You can either correct your thinking or get negative marks ๐Ÿ˜Š
2
2
Just see the question once ; they are saying the DFA accepts strings ends 011 ; it means last state doesnโ€™t have any itself function.
0
0

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.

0
0
1 vote
1 vote

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.

1 comment

Nice
1
1
Answer:

Related questions