Abstract: Radu Gramatovici

THE INFINITE NATURE OF FINITE LANGUAGES

 

           Finite languages have many applications in different areas of applied research and computational models for the implementation of finite languages are often required. Since finite languages are sets with no explicit structure, there are some problems with their implementation. The description complexity of finite languages implemented by deterministic finite automata is usually high. Therefore, the idea of describing (approximating) finite languages by infinite languages has been advocated by Savitch[1989,1993], Marcus[1998] and developed by Cˆampeanu et al[2001], Gramatovici[2000,2002]. In Cˆampeanu et al[2001], finite languages are described by deterministic finite cover-automata, deterministic finite automata which consider a bound in the length of accepted words. But not for all finite languages the switch from deterministic finite automata to deterministic finite cover automata produces a more efficient implementation of the language. In Gramatovici[2000], finite languages are described by bounded deterministic push-down automata, a particular case of deterministic pushdown automata, which consider a bound in the length of the auxiliary stack. It is proved there that the implementation of finite languages by bounded deterministic push-down automata has a smaller description complexity than their implementation by deterministic finite automata or by deterministic finite cover-automata. In Gramatovici[2002], finite languages are described by bounded deterministic go-through automata, which are able to recognize non-context free languages. A go-through automaton has a finite control and uses a sequential auxiliary memory (list). The access discipline of this auxiliary memory allows practically for read/write operations anywhere in the list, but it also keeps some first-in-first-out features, such that, when needed, it works exactly like a push-down automaton. It is proved that the implementation of finite languages by bounded deterministic go-through automata has a smaller description complexity than their implementation by bounded deterministic push-down automata and, implicitly, than their implementation by deterministic finite automata or by deterministic finite cover-automata. Starting from this point on, many other properties have to be discovered and discussed.