Results on Transforming NFA into DFCA

• Autorzy: Câmpeanu C. , Kari L. , Păun A.
• Języki publikacji: EN

Abstrakty

EN

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 [..]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).

Słowa kluczowe

EN

finite automata; deterministic automata; Nondeterministic Finite Automata (NFA); cover automata; state complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 53--63
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Câmpeanu C.

• Department of Computer Science College of Engineering and Science Louisiana Tech. University, Ruston, Louisiana, PO, Box 10348, LA-71272, USA

autor

Kari L.

• Department of Computer Science University of Western Ontario, London, Ontario, Canada, N6A 5B7

autor

Păun A.

• Department of Computer Science, College of Engineering and Science Louisiana Tech University, Ruston, Louisiana, P.O. Box 10348, LA-71272, USA

Bibliografia

• [1] C. Câmpeanu and A. P˘aun, Counting The Number of Minimal DFCA Obtained by Merging States, International Journal of Foundations of Computer Science, 14, 6 (2003), 995–1006.
• [2] C. Câmpeanu, N. Sântean, and S. Yu, Finite Languages and Cover Automata, Theoretical Computer Science, 267, 1-2 (2001), 3–16.
• [3] H. Göeman, On Minimizing Cover Automata in Onlogn Time, in: Proc. of Seventh International Conference on Implementation and Application of Automata, J.M. Champarnaud and D. Maurel, eds., University of Tours, July 2002.
• [4] J. E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading Mass., 1979.
• [5] K. Salomaa and S. Yu, NFA to DFA transformations for finite languages over arbitrary alphabets, Journal of Automata, Languages and Combinatorics, 2 (1997), 177–186.
• [6] N. Sântean, Towards a Minimal Representation for Finite Languages: Theory and Practice, Masters Thesis, The University of Western Ontario, January 2000.
• [7] S. Yu, Regular Languages, in: Handbook of Formal Languages, A. Salomaa and G. Rozenberg, eds., Springer Verlag, Berlin, 1997, 41–110.