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

Riboflavin

I took this class 5 years ago. Give an example of an NFA, would you? – Partnership

An NFA is a state machine where, for a given state and a given input token, there is more than one possibility of a transition. So a NFA could be one where you can get from state 1 to state 2 or state 3 using an 'a', or one with self-loops, or with epsilon-transitions (transitions that require no input token). – Atalya

Do you mean how to programmatically predict the number of states that the DFA will have without actually generating the DFA? It seems to me that any algorithm for predicting the number of states is essentially equivalent to an algorithm that generates the automaton itself, so predicting the number of states won't save you any work. But I'll be pleasantly surprised if someone can tell me differently. I'd think that an NFA with maximal non-deterministic branching would yield the most complex DFA. – Penetrating

Answer 1

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.

Joacimah

@Joacimah -- is there a lower bound proof (link?) -- e.g. family of NFAs for which the minimal DFA accepting the same language grows exponentially in the # of states in the NFA? – Immunize

Answer 2

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

Partnership

I'm not really convinced this is useful. Consider an NFA with states 1, 2, and 3, where there is a transition from 1 to 2 and 1 to 3 on token 'a'. 2 and 3 are final. The resulting DFA has less states and less transitions than the NFA due to merging. So multiplication seems like a step in the wrong direction. – Atalya

I gave you a rough upper bound, because you can conceive an NFA where the worst case does occur. Other than that, you would have to actually convert NFA to DFA and then count the states. This is sort of like saying - I have a program with 10 if statements and no recursion or for loops - how many code paths are there? Well, could be just one code path, but you have to shoot for the worst case and cannot say how many for sure without close inspection, or compiling to assembly and counting jump instructions or what have you ... – Partnership

What do you mean by "n -> n"? Thanks. – Riboflavin

Terrible notation: "n corresponds /maps to n". – Partnership

I wonder if conversion NFA > R.E. > DFA is feasible / helpful for the purposes of simplification. R.E. = regular expression – Partnership

This is answering a different question than asked, as he already knows what the upper bound is. – Devisable

Answer 3

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.

Hillari

Answer 4

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.

Melanosis