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

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

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

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

CC BY-SA 3.0
2014-12-12T11:14:41.583Z
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
CC BY-SA 3.0
2014-12-12T11:15:56.460Z
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
CC BY-SA 3.0
2014-12-12T11:17:08.927Z
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
CC BY-SA 3.0
2014-12-12T16:50:41.247Z
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
CC BY-SA 3.0
2014-12-12T01:50:43.007Z
2014-12-12T01:50:43.007Z
David Eppstein
<p>What is the <strong>worst-case runtime complexity</strong> to transform a NFA to DFA via <strong>Rabin-Scott's power set construction</strong>? Why?</p>

<hr>

<p>Details:</p>

<p><a href="http://en.wikipedia.org/wiki/Powerset_construction">http://en.wikipedia.org/wiki/Powerset_construction</a> states that <strong>the worst-case runtime complexity is $\Theta(2^n)$</strong>, where $n$ is the number of states of the NFA.</p>

<p>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 <strong>the worst-case time complexity would be $\Theta(2^n \times n \times b)$</strong>.</p>

<p>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)$). </p>

<ds.algorithms><automata-theory><time-complexity><exp-time-algorithms>
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?
DaveBall aka user750378
# What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

(Asked by: username_0 on 2014-12-11)

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

**Tags:** ds.algorithms, automata-theory, time-complexity, exp-time-algorithms

---

## 1 answers

### Answer by username_1 on 2014-12-12. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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$.  
> **username_0**: 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.  
> **username_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.  

---

