|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020304,
author = {Kai Salomaa and Sheng Yu},
title = {NFA to DFA Transformation for Finite Languages over
Arbitrary Alphabets},
journal = jalc,
year = 1997,
volume = 2,
number = 3,
pages = {177--186},
keywords = {formal languages, finite automata, state complexity},
abstract = {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.}
}