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

Improve this question
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Apr 25, 2017 at 0:25

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.