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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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$.
For examples and more formal definitions, check the various textbooks and lecture notes detailing this topic (the latter are available online, just google "NFA to DFA").