# Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to transform an NFA to DFA. Thank you.

• this may belong to cstheory.stackexchange.com, flagged accordingly
– Agos
Feb 19, 2011 at 12:00
• @Agos: Dear Agos, the website you mention is for research-level theoretical CS questions. I would expect that this question might be closed there. Feb 19, 2011 at 18:28

Suppose the original NFA had state set $S$, initial state $q \in S$, and accepting states $F \subset S$. The DFA is going to keep track of what possible states the NFA could get into reading the input so far. Therefore each state of the DFA corresponds to a subset of $S$, viz. the possible states the NFA could get into.
The initial state is composed of $q$ and all possible states reachable from $q$ via epsilon transitions. The accepting states are all those containing a state from $F$. The transitions are defined in such a way that the interpretation of states in the DFA conforms to what's written above. In order to see what happens in state $\sigma$ upon reading input $a$, consider for all $s \in \sigma$ all states (if any) reachable by following $a$ and then epsilon transitions; collect all of these, for all $s \in \sigma$, in a set $\tau$, which is the target of the arrow labeled $a$ emanating from $\sigma$.