自动机状态复杂度及模型研究

摘要

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