What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?


Details:

http://en.wikipedia.org/wiki/Powerset_construction states that the worst-case runtime complexity is $\Theta(2^n)$, where $n$ is the number of states of the NFA.

I do not understand how $\Theta(2^n)$ is sufficient: You need up to $2^n$ steps to create the DFA, each creating a new state in the DFA. For each step, you need more time than $\Theta(1)$: you have to consider up to $n$ many states of the NFA (since the DFA-state is a set of up to $n$ states of the NFA) and for each such state up to $b$ (=maximal branching) many outgoing transitions. Thus I would have thought the worst-case time complexity would be $\Theta(2^n \times n \times b)$.

Is there some optimization possible to get to $\Theta(2^n)$? (Above, I have already used the optimization to look in each step at every state of the NFA at most once, instead of iterating through the set of NFA states and for each one doing an epsilon closure with worst case runtime complexity $O(n)$).

up vote 8 down vote accepted

At first glance this looks like a mistake in Wikipedia (it wouldn't be the first one), but I think the time bound there is actually correct, with two assumptions and one small idea.

The assumption is: the alphabet size is constant, so you can ignore the $b$ factor in the runtime and output size. The second assumption is: you can represent the output DFA as a graph in memory, in a conventional adjacency list data structure (or whatever). So in particular to be able to store an edge from one state to another, you need memory cells that can store up to $n$ bits of information per cell, and (in the standard RAM model) this also means constant-time bitwise operations on these cells.

The idea is: each nonempty set of states of the NFA (corresponding to a single state of the DFA) can be formed by adding one element to a smaller set. So, to compute the transitions for a state $S$: find an element $s$ and a state $R$ such that $S=R\cup\{s\}$. Then, for each input alphabet symbol, compute the transition from $S$ as the bitwise Boolean or of the transition from $R$ (previously computed in the same construction) and the transition from $s$ (in the input NFA). Doing this takes $O(b)$ bitwise Boolean operations per state for a total time of $O(1)$ per state.

In practice, you'd probably rather use the version of the construction that only constructs reachable states, rather than all sets. But when you do it that way you can't be guaranteed to find an element whose removal leaves another reachable state, so your $n$ extra factor in the runtime presumably still applies to this version.

  • 1
    Great idea to pick a specific order of the superstates in your construction (+1). This is of course not possible for on-the-fly powerset constructions, which is often the reason to choose the Rabin-Scott algorithm. – DaveBall aka user750378 Dec 12 '14 at 11:14
  • 1
    I do not understand how in your algorithm, you find for each superstate $S$ another superstate $R$ with $S=R \cup \{s\}$ for some NFA state $s$. – DaveBall aka user750378 Dec 12 '14 at 11:15
  • 1
    Furthermore, does your algorithm work for NFAs with epsilon (sometimes called tau) transitions? But I think this problem is already subsumed by my previous comment. – DaveBall aka user750378 Dec 12 '14 at 11:17
  • 1
    You list the superstates in order e.g. as binary numbers. Then for each S the element s can be found as the highest order nonzero bit, which changes only when you reach a new power of two. As I said in my answer, this doesn't work for the version that lists only the reachable states, where you have less choice in evaluation order. As for epsilon-states, you can eliminate them in polynomial time before doing the main algorithm. – David Eppstein Dec 12 '14 at 16:50

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.