alt Hacker NewsNo, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization
No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization
And there are language families where minimal DFA is still exponentially large compared to NFA.