CODEWITHSUNDEEP
theorydfanfanon-deterministicautomaton
xrdty
xrdty

Reputation: 886

NFA to DFA conversion = deterministic?

I am struggling a bit with the meaning of determinism and nondeterminism. I get the difference when it comes to automata, but I can't seem to find an answer for the following: Is a NFA to DFA transformation deterministic?

If multiple DFAs can be constructed for the same regular language, does that mean that the result of a NFA to DFA transformation is not unique? And thus a nondeterministic algorithm?

I'm happy with any information you guys might be able to provide.

Thanks in advance!

Upvotes: 0

Views: 806

Answers (2)

satyananda kumar marada
satyananda kumar marada

Reputation: 1

DFA- means deterministic finite automata Where as NFA- means non deterministic finite automata.. In dfa for every state there is a transition for both the inputs... I we have...{a, b} are the inputs for the given question.. For.. Every state there is a transition for both a and b... That automata is known as deterministic finite automata.. Where as in NDA we need not to have both input transitions for every state... At least one transition... is sufficient... In NFA Epsilon transition is also accepted.. And dead state is also accepted... In nfa... No of states required is less.. When compare to dfa.. Every dfa is equivalent to nfa... But every dfa is not equivalent to nfa...

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372664

There are two different concepts at play here. First, you are correct that there can be many different DFAs equivalent to the same NFA, just as there can be many NFAs that are all equivalent to one another.

Independently, there are several algorithms for converting an NFA into a DFA. The standard algorithm taught in most introductory classes on formal languages is the subset construction (also called the powerset construction). That algorithm is deterministic - there's a specific sequence of steps to follow to convert an NFA to a DFA, and accordingly you'll always get back the same DFA whenever you feed in the same NFA. You could conceivably have a nondeterministic algorithm for converting an NFA to a DFA, where the algorithm might produce one of many different DFAs as output, but to the best of my knowledge there aren't any famous algorithms of this sort.

Hope this helps!

Upvotes: 3

Related Questions