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$
  • 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$ – Yuval Filmus Apr 24 '17 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$ – Yuval Filmus Apr 24 '17 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 '17 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$ – Hendrik Jan Apr 25 '17 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.