● 摘要
自动机理论是研究离散数学系统的结构、作用及其关系的数学理论. 随着现代科技的发展, 计算机科学对基础理论的要求也随之提高, 作为计算机科学中的重要理论, 自动机理论已成为许多学科的理论和应用基础. 自动机作为计算的数学模型, 在计算机科学中的文本处理、编译程序、硬件设计、人工智能等应用领域起着重要的作用. 同时自动机也可以作为语言识别器, 用来研究各种形式语言. 随着Zadah的模糊集理论的提出, 自动机识别语言的能力扩展到了模糊集理论的应用范围, 并随之产生了模糊自动机. 模糊自动机是自动机这个数学模型的一个扩充, 其中包含了像“模糊的”“不准确的”这类概念, 使得自动机识别的语言更接近自然语言, 这在人工智能领域中得到了广泛的应用.
通用自动机是一种特殊的自动机, 每一个正则语言都有其对应的通用自动机, 并且接受该语言的所有自动机都可以通过某种态射的形式映射到它的通用自动机上. 这个性质称为通用自动机的通用性, 这也是通用自动机名字的由来. 通用自动机为研究经典有穷自动机的最小化问题提供了一种新的渠道. 受此启发, 本文提出了通用模糊自动机的概念, 研究了通用模糊自动机的性质, 可以利用通用模糊自动机研究模糊自动机的最小化问题.
本文的主要工作如下:
1.首先对模糊语言进行了研究, 根据模糊语言的性质, 在经典语言分解的基础上, 定义了模糊语言的分解, 进一步定义了模糊语言的左右商, 并且从代数角度出发, 讨论了模糊语言商的性质.
2.在通用自动机的基础上, 提出通用模糊自动机的概念, 利用模糊语言的分解与商的性质, 给出了模糊语言对应的通用模糊自动机的形式化模型. 定义了模糊自动机间的态射, 引入了模糊商自动机、模糊$m$-最小自动机的概念, 比较了模糊商自动机、模糊$m$-最小自动机、模糊最小自动机以及通用模糊自动机之间的关系. 再利用态射讨论了通用模糊自动机的通用性, 并根据通用模糊自动机的通用性对其性质作了进一步的研究. 最后, 对通用模糊自动机进行了等价刻画. 定义了通用模糊自动机的$lambda$-截集, 证明了模糊语言对应的通用模糊自动机的$lambda$-截集恰好是这个模糊语言的$lambda$-截集对应的通用经典自动机.这将通用模糊自动机与通用自动机有效地联系了起来.
相关内容
相关标签