For any finite state automaton A, deterministic or not, size(A) will denote its number of states.

Construct a family (sequence) of NFA's, {N_k}, such that size(N_k) is growing polynomially in k, while size(D_k) is growing exponentially in k, where D_k is the

*minimal*deterministic automaton equivalent to N_k.

Hint: you may use the fact that the sum of the first k primes has polynomial growth, while the product of the first k primes has exponential growth.

## 1 comment:

There should also be an "information-theoretic" proof of the existence of a family of NFA's whose minimal DFA's have exponential size. The argument would proceed by (approximately) counting the number of NFA's vs. DFA's on n states, and showing that there are too many distinct NFA's to have an equivalent small DFA for each. I don't have such an argument formalized but would love to see one; feel free to post them here.

Post a Comment