edited by
7,021 views
7 votes
7 votes

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

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

5 Answers

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 .

edited by
2 votes
2 votes

Answer: b) 4

Three final states and one non-final state.

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.
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.
Answer:

Related questions

1 votes
1 votes
2 answers
1
Satbir asked Jan 13, 2020
2,302 views
Which of the following classes of languages can validate an $\text{IPv4}$ address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ an...
2 votes
2 votes
4 answers
2
6 votes
6 votes
3 answers
3
Satbir asked Jan 13, 2020
3,851 views
The following circuit compares two $2$-bit binary numbers, $X$ and $Y$ represented by $X_1X_0$ and $Y_1Y_0$ respectively. ($X_0$ and $Y_0$ represent Least Significant Bit...