4,753 views

Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is

1. $3$
2. $4$
3. $5$
4. $6$

### 2 Comments

option B is the answer.
because both the strings endling with”101” and not ending with “101” take same number of DFA-states.

pls correct me if Im wrong ;)

## 5 Answers

Best answer

Answer :- B

first make DFA which ends with 101 . then complement it (make initial state as final state and vice-versa)

final answer you will get is this .

Answer: b) 4

Three final states and one non-final state.

### 1 comment

yup, option B is correct .... 4 states are required.
Option B is the correct.

First, try to make DFA for string ending in "101" after that make accepting states Non-Accepting states and vice-versa.

Your problem is solved.
by
Since FOUR state are required to accept the string 101 ,so the complement of the DFA that accept string not ending 101 will have minimum FOUR states.
Answer:

1 vote
2 answers
1
1,180 views
2 votes
4 answers
2
1,103 views
6 votes
3 answers
3
1,901 views
1 vote
2 answers
4