Every state in subset automaton is reachable I'm currently trying to prove that following NFA $\mathcal{M}_0 = (Q, \Sigma, \delta_0,0,\{0\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language. 

$\mathcal{M} = (2^Q,\Sigma,\delta,\{0\},F)$ is constructed using the subset/powerset algorithm and I'd like to show that $\mathcal{M}$ is minimal (i.e. $F = \{q \in 2^Q \mid 0 \in q\}$).

My problem is to show that every state $q \in 2^Q$ is reachable. I'm trying to prove this by induction over $|q|$. 

It is clear for $|q| = 0$ since $\delta(\{0\},b) = \emptyset$. 
For $|q| = 1$ it follows directly from the NFA: $\Delta(\{0\},a^i) = \{i\}$ for $1 \leq i \leq n-2$.

The problem starts in the inductive step. Let $q = \{i_1,\dots,i_k\}$ with $0 \leq i_1 &lt; i_2 &lt; \cdots &lt; i_k \leq n-2$.

For states with $i_1 = 0, i_k=n-2$ (using the induction hypothesis) or $i_1 = 0, i_2=1$ (using the first case mentioned) it is easy to show but in other cases I have no clue how to do it.

EDIT: Beware that the dotted states also have a $b$ loop to themselves (!), i.e. $\delta_0(i,b)=\{0,i\}$ for $1 \leq i \leq n-3$.
Any regular language is accepted by arbitrarily large automata with no inaccessible states. Let $M = (Q, \Sigma, \delta, q_0, F)$ be an automaton with no inaccessible states.  For any natural number $n$, we can write $[n]=\{0, \dots, n-1\}$ and define a new automaton

$$M_n = (Q\times [n], \Sigma, \delta_n, (q_0,0), F\times [n])\,,$$

where $\delta_n((q,i),\sigma) = (\delta(q,\sigma), i+1\bmod n)$ for any $q\in Q$, $i\in[n]$, $\sigma\in\Sigma$.

The effect is that each state counts modulo&nbsp;$n$ the number of characters that have been seen so far, but this has no effect on the behaviour of the automaton, other than making the state space bigger.

The automaton&nbsp;$M_n$ might have inaccessible states, so delete them. But note that, after reading any word of length $0\leq \ell&lt;n$, the automaton is in some state of the form $(q,\ell)$, so at least $n$&nbsp;states are accessible.  Setting $n = 2^{|Q|}$ gives you an exponentially bigger automaton, but why stop there? :-)

Thanks to @holf for the elegant fix to the problem of the disconnected state space.