Saturday, January 20, 2007

A FLAC exercise

This one will almost certainly be assigned. Please do not post answers here.

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:

Leo said...

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.