● 摘要
自动机是计算的简单数学模型, 在计算机科学中有着重要的作用. 最小化问题一直是自动机领域的重要问题之一. 确定型有穷自动机(DFA)的最小化已经得到了有效的算法, 但对于非确定型有穷自动机(NFA)却一直没有得到理想的结果. 剩余有穷自动机(RFA)是基于Myhill-Nerode 定理定义的一类特殊的NFA, 在研究NFA的最小化过程中起到了十分重要的作用, 为自动机最小化研究探索出了一条新的途径.
1965年, L. A. Zadeh 提出了模糊集理论, 1967年, W. G. Wee 将模糊集的概念引入到了自动机理论中. 随后, 模糊自动机便得到了广泛的研究.模糊有穷自动机可以看做是经典自动机的一个扩充,其中包含了像“大约”“高”“矮”这类模糊的、不准确的概念, 即就是在自然语言中经常用到的一些模糊语言. 正如经典的自动机那样, 最小化问题依然是模糊自动机的核心问题之一,虽然确定型模糊自动机的最小化已经有了很好的结果, 但是非确定型模糊自动机的最小化问题还有待研究.
由于RFA在研究经典自动机的最小化问题中起到了重要作用, 我们考虑利用类似的方法进行模糊自动机的最小化研究. 本文在完备剩余格上定义了 一种重要的模糊自动机(LFA)类型-模糊剩余有穷自动机(LRFA). LRFA 是一类特殊的 LFA, 确定型模糊有穷自动 机 (DLFA) 是特殊的 (LRFA). 通过定义标准 LRFA来实现LRFA的最小化. 本文的主要工作如下:
1. 给出了模糊剩余语言(LRL)的概念, 讨论了LRL的基本运算和基本性质, 利用LRL给出构造最小DLFA的方法. 结合 LRL给出 LRFA的定义, 讨论了LRFA的一些重要的性质.在以上定义的基础上, 利用 截集对LRFA进行了讨论, 有效的将LRFA与RFA联系起来, 即LRFA的 截集是RFA.
2. 讨论了$LRFA$ 的最小化问题, 定义了$LFA$ 的饱和运算与消去运算, 讨论了两种运算相关的一些重要性质, 特别的, $LRFA$ 经过这两种运算后依然是$LRFA$; 在定义饱和运算与消去运算的基础上给出了标准LRFA的概念, 证明了标准LRFA是状态最小的惟一LRFA以及标准LRFA拥有比识别相同语言的最小DLFA更少的状态数; 讨论了DLFA、LRFA以及LFA 识别语言的包真含关系, 并在 LFA$转化为 DLFA算法的基础上, 给出了LFA$转化为DLFA的算法.
相关内容
相关标签