There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton
"the language of strings over the alphabet {0,1} in which there are at least n characters, the nth from last of which is 1. It can be represented by an (n + 1)-state NFA, but it requires 2n DFA states, one for each n-character suffix of the input."
Comments
There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton
Can anyone provide one such example, please?
"the language of strings over the alphabet {0,1} in which there are at least n characters, the nth from last of which is 1. It can be represented by an (n + 1)-state NFA, but it requires 2n DFA states, one for each n-character suffix of the input."
http://en.wikipedia.org/wiki/Powerset_construction#Complexit...
For reference, that "2n" is supposed to be 2^n.
Thanks for catching that.