Research On State Complexities And Models Of Automata

Theoretical computer science had its beginnings in a number of diverse fields: biologists studying models for neuron nets, electrical engineers developing switching theory as a tool to hardware design, mathematicians working on the foundations of logic, and linguists investigating grammars for natural languages. Automata theory is the foundation of computer science. Its applications have spread to almost all areas of computer science and many other disciplines, such as switching theory, pattern recognition, speech processing, hand writing recognition, optical character recognition, encryption algorithm, data compression, indexing and operation system analysis(Petri-net).Finite-state devices, which include finite-state automata and finite-state transducers, are in wide use in many areas of computer science. Recently, there has been a resurgence of the use of finite-state devices in all aspects of computational linguistics, including dictionary encoding, text processing, and speech processing.In the applications of finite automata, it is very necessary to know the storing space of automata. This is the issue of state complexity research. In fact, the state complexity research started very early, however before 1990's there were not so many research results in this area since there were no efficient tools for automata implementation. Since the last two decades, some computer software for implementing automata came into being. It fosters state complexity research. Meanwhile, finite automata have more and more new applications in different areas and usually the sizes of automata in new applications are large. State complexity research has big significance from both theoretical point of view and practical point of view. On the other hand, new models of computation should be introduced due to some purpose such as the traditional models are not so powerful in some aspects. There is a good example that context-free grammars and languages are not enough to express all the phenomenon in natural language. Thus we try to induce new automata models and examine the computational power of existing tools in this dissertation.In this dissertation, we intend to investigate several basic problems in formal language and automata theory. The state complexities of some combined operations are obtained. We introduce the fuzzy tree automata system by giving the fuzzy function from an algebra to a completely distributive lattice.The main achievements of this dissertation are as follows:1. State complexities of some combined operations, some basic operations combined with reversal, are investigated. We obtain the state complexities of these combined operations by constructive method based on automata implementation software grail+. Both the upper bounds and worst-case examples are given. It has great significance to the application of large size automata.2. Upper bounds of the number of states for the minimal automata for star combined with some basic operations are obtained. However, we haven't figured out worst-case examples for these cases. This means that whether these upper bounds are tight, there is no answer so far.3. Based on the surveying of automata theory including finite automata, tree automata and weighted automata, we define algebra of fuzzy functions by mapping arbitraryΣ-algebras to completely distributive lattices. Also, we define rational fuzzy sets. We prove that a fuzzy set is equational if and only if it is rational. Given fuzzy transitions to a tree automaton, we obtain the definition of fuzzy tree automata. The representation of Kleene's theorem for fuzzy recognizable set is obtained.The outline of future work is presented at the end of this dissertation.