7 votes 7 votes Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is $3$ $4$ $5$ $6$ Theory of Computation isro-2020 theory-of-computation finite-automata normal + – Satbir asked Jan 13, 2020 edited Jul 22, 2023 by Lakshman Bhaiya Satbir 7.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Sanandan commented Sep 1, 2020 reply Follow Share option B is the answer. 0 votes 0 votes Vishnu__ commented Oct 1, 2022 reply Follow Share because both the strings endling with”101” and not ending with “101” take same number of DFA-states. pls correct me if Im wrong ;) 0 votes 0 votes Deepak Poonia commented Jul 22, 2023 reply Follow Share $\color{red}{\text{Detailed Video Solution:}}$ https://youtu.be/VE71CxKb390 0 votes 0 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes 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 . shivam001 answered May 7, 2020 edited Jul 22, 2023 by Deepak Poonia shivam001 comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Answer: b) 4 Three final states and one non-final state. Tuhin Dutta answered Jan 13, 2020 Tuhin Dutta comment Share Follow See 1 comment See all 1 1 comment reply scholaraniket commented Jan 20, 2020 reply Follow Share yup, option B is correct .... 4 states are required. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 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. Parth27 answered Jan 24, 2020 Parth27 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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. DIBAKAR MAJEE answered May 7, 2020 DIBAKAR MAJEE comment Share Follow See all 0 reply Please log in or register to add a comment.