If a language (L) is recognized by an n-state NFA, can it also be recognized by a DFA with no more than 2^n states?

I'm thinking so, because the upper bound would be the 2^n, and given that these are both finite machines, the intersection for both 开发者_高级运维the n-state NFA and the DFA with 2^n or less states will be valid.

Am I wrong here?

You're right. 2^n is an upper limit, so the generated DFA can't have more states than that limit. But it's the worst-case scenario. In most common scenarios there's less states than that in the resulting DFA. Sometimes it could be even less than in the original NFA.

But as far as I know, the algorithm to predict how many states the resulting DFA will actually have, doesn't exist yet. So if you'll find it, please let me know ;)

That is correct. As you probably already know, both DFAs and NFAs only accept regular languages. That means that they are equal in the languages they can accept. Also, the most primitive way of transforming a NFA to a DFA is with subset construction (also called powerset construction), where you simply create a state in the DFA for every combination of states in the NFA. This is called the powerset of states, which could at most be 2^n.

But, as mentioned by @SasQ that is the worst case scenario. Typically you will not end up with that many states if you use Hopcroft's algorithm or Brozowski's algorithm.