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 was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and especially the proof of such a statement.

share|improve this question
    
Yes. See en.wikipedia.org/wiki/Powerset_construction, which works for any NFA (including those with lambda transitions). –  Patrick87 Oct 25 '12 at 18:25
add comment

2 Answers

up vote 2 down vote accepted

Indeed, every NFA can be converted to an equivalent DFA. In fact, DFAs, NFAs, and regular expressions are all equivalent. One approach would be to observe the NFA and if it simple enough, determine the regular expression that it recognizes, then convert the regular expression to a DFA.

Yet, there are algorithms out there that can take a NFA and produce its equivalent DFA. For example, the powerset construction check out this link and google:

http://en.wikipedia.org/wiki/Powerset_construction

Furthermore, every DFA has a unique minimum state DFA that recognizes a regular expression using a minimal number of states. This DFA state minimization also has an algorithm.

Good luck!

share|improve this answer
add comment

It can be done in two steps:
1) Use subset construction to construct DFA from NFA.
2) Then show for any w $\in$$\sum$$^*$,
$\hat\delta$$_D$({q},a) = $\hat\delta$$_N$(q,a). That is for any string and for any set of states they both take you to same set of states.

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.