Most non-deterministic automaton

Question

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.

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.

Answer 1

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; he notes that it is of unknown origin.