ISRO CSE 2020 | Question: 41

Question

Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is

• A. $3$
• B. $4$
• C. $5$
• D. $6$

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 ;)

---

$\color{red}{\text{Detailed Video Solution:}}$ https://youtu.be/VE71CxKb390 

Answer 1

Answer :- B

First make DFA which recognizes binary strings ending with 101, then complement it (make non-final states as final states and vice-versa) 

final answer you will get is this .

Answer 2

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.

Answer 3

Answer: b) 4

Three final states and one non-final state.

Comments

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

Answer 4

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 5

Answer-B 4, First make a DFA which accepts a string ending with "101" . After that compliment the DFA.
Note: You can compliment the DFA by making non final states as final and final states as non final.