in Theory of Computation edited by
4,753 views
6 votes
6 votes

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

  1. $3$
  2. $4$
  3. $5$
  4. $6$
in Theory of Computation edited by
by
4.8k views

2 Comments

option B is the answer.
0
0
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
0

5 Answers

5 votes
5 votes
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 .

selected by
2 votes
2 votes

Answer: b) 4

Three final states and one non-final state.

1 comment

yup, option B is correct .... 4 states are required.
0
0
1 vote
1 vote
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