
Cezar Campeanu, Lila Kari, Andrei Paun. Results on Transforming NFA into DFCA. Fundamenta Informaticae, 64, Number 14, pp. 53  63, 2005.
Abstract:
In this paper we consider the transformation from (minimal) nondeterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from nondeterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blowup state complexity of DFA and DFCA can be as small as 2[n/2]−² compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blowup complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).
Keywords:
nondeterministic automata, cover automata, state complexity, Finite automata, deterministic automata
URL:
http://iospress.metapress.com/app/home/contribution.asp?referrer=parent&backto=issue,6,39;journal,34,88;linkingpublicationresults,1:300178,1
Posted by
Cezar Campeanu
Back
