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.

Improve this question
$\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$ – Yuval Filmus Jan 19 '17 at 13:52
  • 2
    $\begingroup$ You can add an arbitrary number of states to an NFA without changing the language it recognizes. $\endgroup$ – adrianN Jan 19 '17 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 Jan 20 '17 at 7:08
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.)

Improve this answer
$\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.