2
$\begingroup$

I was just thinking about the powerset construction and it is clear to me that the powerset construction will result into a DFA $D$ with possibly redundant states, as the NFA $N$ is not minimized. But in case where $N$ is minimal will $D$ will also be minimal?

So is there a DFA $D'$ with less states for the same Language $L$, assuming that only accessible states are added to $D$? I think it cannot be, since a redundant state in $D$ would result into a redundant edge in $N$ and this would contradict the assumption, but I am not sure.

Thanks.

$\endgroup$
4
  • 3
    $\begingroup$ What is the powerset construction for you? Do you only construct the reachable states? Otherwise the claim is plainly false, since you can construct languages whose minimal DFA contains a number of states which is not a power of 2. $\endgroup$ Apr 24, 2017 at 19:42
  • 3
    $\begingroup$ Even if you only construct the reachable states, the answer is most probably no, and it is probably not difficult to find an example. $\endgroup$ Apr 24, 2017 at 19:43
  • 3
    $\begingroup$ I suggest you spend some time working through some simple examples of small NFAs, to see if you can find a counterexample. $\endgroup$
    – D.W.
    Apr 24, 2017 at 19:50
  • $\begingroup$ There is no unique minimal NFA for a regular language in general: cs.stackexchange.com/a/12694/4287 For DFA the minimal automaton is unique. $\endgroup$ Apr 25, 2017 at 0:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.