Descriptional complexity of determinization and complementation for finite automata
Aniruddh Gandhi, Nan Rosemary Ke, Bakhadyr Khoussainov · Computing: The Australasian Theory Symposium · 2011
In this paper we study the subset construction that transforms nondeterministic finite automata (NFA) to deterministic finite automata (DFA). It is well known that given a n-state NFA, the subset construction algorithm produces a 2n-state DFA in the worst case. It has been shown that given n, m (n 1 and n > k), the NFA recognizing these languages need n states and the NFA recognizing their complement needs (k + 1)n − (k + 1)2 + 2 states. Finally we show that for given n, k > 1, there exists a O(n)-state NFA A such that the minimal NFA recognizing the complement of L(A) has between O(nk−1) and O(n2k) states. Importantly however, the constructed NFA's have a small number of transitions, typically in the order of O(n) or O(n2/log2(n)). These are better than the comparable results in the literature.