NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets
Kai Salomaa, Sheng Yü · Universitätsbibliothek Gießen · 1997
We consider the number of states of a DFA that is equivalent to an $n$-state NFA accepting a finite language over an arbitrary alphabet. We show that, for any $n$-state NFA accepting a finite language over a $k$-letter alphabet, $n,k > 1$,there is an equivalent DFA of $O(k^{n/(\log_2 k+1)})$ states, and show that this bound is optimal in the worst case.