-1
$\begingroup$

Is there a unique DFA for every NFA or there are more than one DFA an NFA can be converted to? I've read the algorithm for converting NFA to DFA.

$\endgroup$
2
$\begingroup$

You say you are familiar with the standard subset construction that turns an NFA into a DFA. Let's start from there. If you study some examples you may realize that the result is not optimal. By "trimming" you might obtain a "better" DFA that still is equivalent.

In the first example you see that not all sets in the construction are reachable from the initial state. Of course those states can be deleted without changing the language. (top NFA, bottom DFA, unreachable states grayed out in the figure)

enter image description here

In my second example all states are reachable, but there is a "cluster" of states at the end, all of them which are accepting (states that contain "F"). Those states can all be indentified. This will give you a smaller equivalent DFA.

enter image description here

Although there is no unique DFA for a given regular language, it turns out that there is a unique minimal DFA for the language. That is the topic of DFA minimization algorithms.

$\endgroup$
1
$\begingroup$

There is more than one DFA. Just add a useless state with transitions from it to the other states. With no way to reach this useless state, the new DFA will be equivalent.

There are in fact an infinite amount of equivalent DFA's.

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