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.
Subscribe to:
Post Comments (Atom)
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