2
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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").

$\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.