1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
2
$\begingroup$

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:

Example DFA

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.