554 views

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$

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

indeed it is good doubt...

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

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

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.

by

edited

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?

@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

1
582 views