2
$\begingroup$

Assume I have a DFA with 20 states, is it possible to know the maximum number of states of the NFA which it was converted from?

I know that the minimal number of states would be 5 (because you cannot have created a DFA with 20 states from an NFA with 4 states).

But I don't really understand how can I know if there's a maximum that can be determined.

$\endgroup$
3
  • 1
    $\begingroup$ The answer depends on the algorithm you use to convert the NFA to a DFA. Do you have any particular algorithm in mind? $\endgroup$ Commented Jan 19, 2017 at 13:52
  • 2
    $\begingroup$ You can add an arbitrary number of states to an NFA without changing the language it recognizes. $\endgroup$
    – adrianN
    Commented Jan 19, 2017 at 13:58
  • $\begingroup$ I'm using the regular NFA to DFA convertion algorithm (the one that could produce 2^n max states in the DFA ) $\endgroup$
    – shaqed
    Commented Jan 20, 2017 at 7:08

1 Answer 1

3
$\begingroup$

No, because there is no maximum. There are infinitely many NFA's that are all equivalent and accept the same language. For instance, you can take any NFA you think it might have come from and add some extra disconnected states, and the new NFA will also have the same language and thus could correspond to the same DFA.

(Your only hope is that if you know exactly what conversion procedure was used, and if the conversion procedure retains useless states and forms a bijection from NFAs to DFAs, then maybe. But in practice I would not expect ordinary conversion procedures to have that property.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.