【作者】 刘光武；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统工程， 2007， 博士

【摘要】 理论计算机科学在很多不同领域有其根源:生物学家研究神经网的模型,电气工程师发展交换理论用以作为硬件设计的工具,数学家对逻辑学基础进行的研究,语言学家研究表达自然语言语法的模型,都可以看作是理论计算机科学的研究范畴。自动机理论是计算机科学的基础,其应用已渗透到计算机科学的几乎各个领域和其他的一些学科,例如交换理论、模式匹配与模式识别、语音处理、手写体识别、光学字符识别、密码算法、数据压缩、操作系统分析。有限状态机器(包括有限状态自动机及有限状态转换机)被应用于计算机科学的许多领域,最近又出现了将有限状态机器用于计算语言学各个方面的潮流,包括字典编码、文本处理及语音处理。在有限状态自动机的应用中,非常重要的一个问题是存储空间的问题,这就是有限状态自动机状态复杂度研究所考虑的问题。实际上,有限状态自动机状态复杂度的研究早已开始,然而在上世纪九十年代以前由于没有合适的有效工具用来实现自动机的操作,因此在这一领域的研究结果其少。但是自从近二十年来,出现了一些用来操作自动机的计算机辅助软件,使得可以用计算机来完成自动机上的操作,这大大推动了对自动机状态复杂度的研究。同时有限状态自动机在许多不同领域有着越来越多的新应用而且在这些新应用中自动机的尺寸通常都非常大,在这种情况下自动机状态复杂度的研究既有着非常重要的理论意义也有着显著的实用价值。另一方面,由于传统计算模型在某些方面的限制不足以描述指定的问题,有必要引入新的计算模型或者研究现有模型的新特性,一个很好的例子是上下文无关文法和语言就不可能表达自然语言中的所有现象,因此本文也试图引入一种新的自动机模型及研究现有工具的语言计算能力。本文研究了形式语言与自动机理论中的几个基本问题。对有限自动机上几个复合操作的状态复杂度进行了研究;通过定义从一个代数结构到完全分配型网格的模糊函数的方法引入了模糊树自动机模型。本文的主要贡献在于研究了以下几个方面的问题:1.研究了有限状态自动机上一些基本操作与逆转进行复合运算的状态复杂度,在现有操作自动机的辅助软件grail+的基础上用构造性的方法证明了这些复合操作的状态复杂度,证明了这些操作状态复杂度上界的同时还给出了极坏情况下的实例,这对于大尺寸自动机的成功应用具有非常重要的意义。2.证明了有限状态自动机上星操作和一些基本操作进行复合运算的状态复杂度上界,然而目前为止还未能得到这些复合操作能达到这些上界的极坏情况实例,这有待于在今后的工作中进一步进行研究。3.在回顾现有自动机理论的基础上,引入了模糊树自动机的模型。通过定义从一个任意∑代数到一个完全分配型网格的映射的方法定义了模糊函数(即模糊集)的代数,在模糊函数的代数中定义了布尔操作,从而使得模糊集函数的代数也具有网格的结构。同时,还定义了有理模糊集,证明了一个模糊集为等式模糊集当且仅当其为有理模糊集。通过将树自动机的转移函数模糊化定义了模糊树自动机模型,给出了克林定理关于模糊可识别集的表达形式。在本文的最后给出了今后研究工作的方向和重点。更多还原

【Abstract】 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.更多还原