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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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:
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.
It can be done in two steps: