Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
this may belong to cstheory.stackexchange.com, flagged accordingly –  Agos Feb 19 '11 at 12:00
2  
@Agos: Dear Agos, the website you mention is for research-level theoretical CS questions. I would expect that this question might be closed there. –  Akhil Mathew Feb 19 '11 at 18:28
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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