# How are useless states created NFA to DFA

So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA without creating any useless states?

Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $$a$$. If we make it determinsitic using the standard construction half of the states will be unreachable.

You ask, why does this happen? Look at the initial state $$0$$ of the original automaton. It has a loop for both $$a$$ and $$b$$. That means that in the powerset construction all next states will always contain state $$0$$ because the deterministic automaton collects the states of all paths from the original automaton. As a consequence all states without $$0$$ are uneachable. It is possible "by hand" to avoid those unreachable states, by a step by step construction. Only consider staes that are reached and continue form those to the next possible states. A kind of depth-first construction will work.

If the construction method supports "negative" regular expression operators, such as set intersection or set difference, it's likely that the method will produce useless states. For example, Brzozowski's method, when given the expression $$\left(a \cup b\right)^* \setminus \left( a \left( a \cup b\right)^* \right)$$, will likely produce something like this: The branch $$q_2$$ corresponds to the "removed" subexpression $$a \left( a \cup b\right)^*$$. (Note that this is a DFA.)

The typical way to eliminate useless states in real-world DFA generators is to use DFA minimisation. In the minimal DFA, all useless states map to a single state, so there's only one state to remove.