# Most non-deterministic automaton

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.

• 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. cs.stackexchange.com/questions/6063/… Aug 4, 2022 at 17:44

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.
• 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. Aug 14, 2022 at 15:25