NFA to DFA 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 开发者_StackOverflow中文版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".

---

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.

---

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 ...

---

Take as a function of N, with start state S and final state N, this NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

It should be obvious that this accepts all strings in [ab]* whose Nth-from-last letter is a.

The determinization of A(N) has to remember the previous N-1 letters, effectively (you need to know all the positions in that window that were a, so that when the string unexpectedly ends, you can say whether there was an a N letters ago).

I'm not sure if this hits exactly the number of states you wanted, but it's at least within a factor of 2 - all subsets of {0,...,N} are possible, but you're also always in S. This should be 2^(N+1) states, but A(N) had N+2 states.

---

To further expand on the excellent answer of Jonathan Graehl.

Add to each state 0, 1, ..., N of A(N) a selfloop labeled c, i.e., you add the following transitions:
0 c-> 0
1 c-> 1
...
N c-> N

Then assuming c never fires, the DFA contains the same 2^(N+1) states of Jonathan's DFA. However, whenever c is observed from a state {S,j,k,...,z} <> {S} we reach state {j,k,...,z}. Hence all subsets of {S,0,...,N} are possible except the empty set and the DFA has 2^(N+2)-1 states while A(N) has N+2 states.