3 ms·
There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton Can any
by ced 13y ago
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?
- prutschman 13y ago"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#Complexity http://en.wikipedia.org/wiki/Powerset_construction#Complexit...
- comex 13y agoFor reference, that "2n" is supposed to be 2^n.
- prutschman 13y agoThanks for catching that.