Affiliations: Department of Computer Science and Information
Technology, University of Prince Edward Island, Charlottetown, P.E.I., Canada,
C1A 4P3. cezar@sun11.math.upei.ca | Department of Computer Science, University of Western
Ontario, London, Ontario, Canada, N6A 5B7. lila@csd.uwo.ca | Department of Computer Science, College of Engineering
and Science, Louisiana Tech University, Ruston, Louisiana, P.O. Box 10348,
LA-71272, USA. apaun@latech.edu
Note: [] Address for correspondence: Department of Computer Science,
College of Engineering and Science Louisiana Tech University, Ruston,
Louisiana, P.O. Box 10348, LA-71272, USA
Abstract: In this paper we consider the transformation from (minimal)
non-deterministic 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
non-deterministic 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 blow-up state complexity of DFA and DFCA can be as
small as 2⌈n/2;⌉−2 compared to the number of states of the
minimal DFA. Moreover, we show the structure of automata for worst case
exponential blow-up 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).
