NFA to DFA question

Question

First, this is not a question asking for the algorithm to convert a NFA to DFA.

It's known (and proved) that the equivalent DFA of a NFA has at most 2ⁿ states, even though most of the times it will have more or less the same number of states as the NFA.

How may I predict an estimate for the number of states the NFA-equivalent DFA will have? Which particular type of NFA will require an equivalent DFA to have 2ⁿ states?

My reason for asking this is to be able to "invent" some NFAs that will certainly produce, without considering minimization, 2ⁿ - 1 states plus the "dead state".

Answer 1

Ok, start with assumption that n -> n. Now, for every non-deterministic transition where from one state you can end up in x other states, multiply your estimate by x. This may not be precise, as you might double-count. But it should give you an upper bound.

However, the only sure way it to build a corresponding DFA and then count the states (I think).

Finally, you can probably simplify some of the DFAs (and NFAs for that matter), but this is a whole new story ...

Answer 2

The number of states explodes due to non-determinism, which is the key to your question.

If you take an NFA, where each transition is uniquely determined, i.e. a deterministic NFA, then it is nothing but a normal DFA. However, once you have a state where two transitions are possible it differs from the DFA.

Consider the conversion algorithm and look at what happens if you have two or more transitions with the same label for a state. This is where you need those new states that correspond to sets of states.

So the question comes down to finding out how many of these superset states are actually reachable. Of course you could invent a fancy algorithm for that, but to get the correct number, simply run the normal conversion algorithm and remove unreachable states.

As for an NFA with n states for which the equivalent DFA has 2^n states think about exploiting non-determinism. The first idea would be to label all transitions the same, however, that doesn't work out too well. Instead remember that you need to be able to somehow reach all subsets of states with some label each.

If you do not count the starting state, then you can do the following construction: create n nodes and for each set out of 2^n create a unique label and in the NFA add a transition with this label to each node of that set. This gives you a NFA with n+1 states (1 being the starting state), where the DFA requires 2^n +1 states. Of course, it gets trickier, once you want to have 2^n DFA states after minimization.