in Theory of Computation edited by
554 views
6 votes
6 votes

An NFA has $10$ states out of which $3$ are final states. The maximum number of final states in converted DFA is:

  1. $895$
  2. $894$
  3. $896$
  4. $897$
in Theory of Computation edited by
by
554 views

4 Comments

has this question been asked in some exam ?
0
0
yes, i agree, there is no way to predict ..but in question nothing such case/ possibility is mention ..

indeed it is good doubt...
0
0

yes, it came in Gate 2008, in different way though..see this 

https://gateoverflow.in/3266/gate2008-it-6

0
0

1 Answer

10 votes
10 votes
Best answer

There are 3 final states in total 10 states .

7 are non final states , so all these state which come together to form a state in dfa are not have any finale state in dfa.  .

so possible DFA state with only these 7 Non final states are 27 = 128

and total 210  =  1024 states are possible 

so total number of state which contain final state is 1024 - 128 = 896

option C is true here.

selected by

2 Comments

edited by

Sir

lets take 1,2,3.....7 non final and 8,9,10 final

{1,2,3.....7} subset correspond to non final okk. total subset 2which contain {} also.so {} can be state in dfa??

plz tell whats wrong?

0
0

@Abhisek Tiwari 4; please note that the states are provide for NFA.
When we convert NFA to DFA; if there is a transition in NFA which goes to Φ or empty; then in corresponding DFA it is a reject state.

Thus the subset can consist of a Φ state.

I attempted this question in a bit longer method:
Number of final state is 3 (8,9,10)
Number of non-final state is 7
Since, Accepted state consist of one or more combination of 8,9,10 (2^3 combinations - 1 {removing the Φ state as then there will be no combination of final state and this will not be final sate in DFA}) and 0 or more combinations of 1 to 7 (2^7): total = 2^3 * (2^7-1) = 7*128 = 896

0
0
Answer:

Related questions