<p>Here is a construction over a binary alphabet, which moreover yields a <em>minimal</em> DFA of size <span class="math-container">$2^n$</span>.</p>
<p>Consider the NFA over <span class="math-container">$\Sigma=\{a,b\}$</span> with states <span class="math-container">$[n]=\{1,\dots,n\}$</span> such that the starting state is <span class="math-container">$1$</span>, the only accepting state is <span class="math-container">$n$</span>, and with transitions <span class="math-container">$i\overset a\longrightarrow i+1$</span>, <span class="math-container">$i\overset b\longrightarrow i$</span>, and <span class="math-container">$i\overset b\longrightarrow1$</span>.</p>
<p>The powerset construction yields a DFA with states <span class="math-container">$\mathcal P([n])$</span> with transition functions
<span class="math-container">$$T_a(X)=\{i:i-1\in X\},\qquad T_b(X)=X\cup\{1\},$$</span>
from which it is easy to see that every <span class="math-container">$X\in\mathcal P([n])$</span> is reachable from the initial state <span class="math-container">$\{1\}$</span>. Moreover, this DFA is minimal: if <span class="math-container">$X\ne Y$</span>, there is <span class="math-container">$i\in X$</span> such that <span class="math-container">$i\notin Y$</span> or vice versa; then <span class="math-container">$a^{n-i}$</span> takes <span class="math-container">$X$</span> to an accepting state, but <span class="math-container">$Y$</span> to a non-accepting state.</p>
<p>EDIT: It turns out a similar construction is given by Jean-Éric Pin <a href="https://cs.stackexchange.com/a/16287">here</a>; he notes that it is of unknown origin.</p>

CC BY-SA 4.0
2022-08-14T15:25:00.490Z
Meanwhile I've found another (somwhat similar) construction in Jacques Sakarovitch "Elements of automata theory" page 194: $Q=\{0,\dots,n-1\}$, every state is initial, $i \cdot a = i + 1$ mod $n$, for $i\in Q$, $i \cdot b = i$, for $i=1,\dots,n-1$ and $\delta(0,b)$ is undefined.
user6767509
CC BY-SA 4.0
2022-08-05T12:03:24.353Z
2022-08-06T09:09:26.553Z
2022-08-06T09:09:26.553Z
Emil Jeřábek
<p>My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly <span class="math-container">$2^n$</span> reachable states (even thought we might be able to minimize the automaton). What I've seen about converting an NFA to a DFA is a power set contruction, but in every example there are always unreachable states in the DFA, so if you construct it creating only the states you can reach, it ends up having less than <span class="math-container">$2^n$</span> states, without even being minimized.</p>
<p>So I thought about constructing NFAs where the power set construction gives you the worst possible DFA - one with exactly <span class="math-container">$2^n$</span> states. I thought it was interesting because it is as if you have the &quot;most non-deterministic&quot; automaton, in the sense that the conversion leads you to the worst case of the number of required states to simulate the NFA with a DFA (I'd like to point out that I'm not concerned with the fact that the DFA may be minimizable - that sounds interesting, but a bit harder to check).</p>
<p>Below are two examples, for <span class="math-container">$n=2$</span> and <span class="math-container">$n=3$</span>, where the DFA you obtain using the power set construction has <span class="math-container">$2^n$</span> reachable states.</p>
<p><a href="https://i.sstatic.net/ALo57.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ALo57.png" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/LA17A.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LA17A.png" alt="enter image description here" /></a></p>
<p>So, is there a &quot;uniform&quot; construction for these non-deterministic automata? In these examples I just went on adding transition to create all the states in the power set, but I always had to check what I had and what I was still missing.</p>

CC BY-SA 4.0
2022-08-04T17:44:02.953Z
Do you really need precisely 2^n states or O(2^n) states? The other question is a school exercise, which is unsuitable for this webpage. https://cs.stackexchange.com/questions/6063/how-to-prove-that-dfas-from-nfas-can-have-exponential-number-of-states
Bartosz Bednarczyk
<automata-theory><nondeterminism>
Most non-deterministic automaton
user6767509
# Most non-deterministic automaton

(Asked by: username_0 on 2022-08-04)

My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly $2^n$ reachable states (even thought we might be able to minimize the automaton). What I've seen about converting an NFA to a DFA is a power set contruction, but in every example there are always unreachable states in the DFA, so if you construct it creating only the states you can reach, it ends up having less than $2^n$ states, without even being minimized.

So I thought about constructing NFAs where the power set construction gives you the worst possible DFA - one with exactly $2^n$ states. I thought it was interesting because it is as if you have the "most non-deterministic" automaton, in the sense that the conversion leads you to the worst case of the number of required states to simulate the NFA with a DFA (I'd like to point out that I'm not concerned with the fact that the DFA may be minimizable - that sounds interesting, but a bit harder to check).

Below are two examples, for $n=2$ and $n=3$, where the DFA you obtain using the power set construction has $2^n$ reachable states.

[![enter image description here](https://i.sstatic.net/ALo57.png)](https://i.sstatic.net/ALo57.png)

[![enter image description here](https://i.sstatic.net/LA17A.png)](https://i.sstatic.net/LA17A.png)

So, is there a "uniform" construction for these non-deterministic automata? In these examples I just went on adding transition to create all the states in the power set, but I always had to check what I had and what I was still missing.

**Tags:** automata-theory, nondeterminism

> **Comments:**
> **username_1**: Do you really need precisely 2^n states or O(2^n) states? The other question is a school exercise, which is unsuitable for this webpage. https://cs.stackexchange.com/questions/6063/how-to-prove-that-dfas-from-nfas-can-have-exponential-number-of-states  

---

## 1 answers

### Answer by username_2 on 2022-08-05. Score: 5 | Accepted answer

Here is a construction over a binary alphabet, which moreover yields a *minimal* DFA of size $2^n$.

Consider the NFA over $\Sigma=\{a,b\}$ with states $[n]=\{1,\dots,n\}$ such that the starting state is $1$, the only accepting state is $n$, and with transitions $i\overset a\longrightarrow i+1$, $i\overset b\longrightarrow i$, and $i\overset b\longrightarrow1$.

The powerset construction yields a DFA with states $\mathcal P([n])$ with transition functions
$$T\_a(X)=\{i:i-1\in X\},\qquad T\_b(X)=X\cup\{1\},$$
from which it is easy to see that every $X\in\mathcal P([n])$ is reachable from the initial state $\{1\}$. Moreover, this DFA is minimal: if $X\ne Y$, there is $i\in X$ such that $i\notin Y$ or vice versa; then $a^{n-i}$ takes $X$ to an accepting state, but $Y$ to a non-accepting state.

EDIT: It turns out a similar construction is given by Jean-Éric Pin [here](https://cs.stackexchange.com/a/16287); he notes that it is of unknown origin.

> **Comments:**
> **username_0**: Meanwhile I've found another (somwhat similar) construction in Jacques Sakarovitch "Elements of automata theory" page 194: $Q=\{0,\dots,n-1\}$, every state is initial, $i \cdot a = i + 1$ mod $n$, for $i\in Q$, $i \cdot b = i$, for $i=1,\dots,n-1$ and $\delta(0,b)$ is undefined.  

---

