in Theory of Computation
1,772 views
2 votes
2 votes
If NFA has n states, then its DFA can have______states in worst case.
in Theory of Computation
by
1.8k views

2 Answers

1 vote
1 vote

2N  states in maximum case 

by

1 comment

Won't that be less than 2^n.

i.e (2^n) - 1
0
0
0 votes
0 votes
2^N

Reason;

The next state of nfa coud be any subset of state .

no of subset of states=2^n(as we have 2 choices for each state either we can keep it or not in our subset )

Related questions

0 votes
0 votes
1 answer
1