作为计算理论中最简单的数学模型,有限自动机不仅是复杂性理论的理论基础,而且与其他领域密切相关,例如神经网络、模式识别、密码算法,以及操作系统分析等.近年来,随着模糊技术的快速发展,由模糊系统理论和有限自动机交叉融合构成的模糊有限自动机和模糊语言发展迅速,它们不仅合理地拓展了有限自动机和语言理论,而且具有很重要的实用价值,例如在学习系统、模式识别、数据库理论,以及离散事件系统等方面都有着重要的应用.基于完备剩余格值逻辑自动机理论-L-值有限自动机(L-VFAs)理论已经系统地建立起来,该理论推广了代数模糊自动机理论,为计算理论提供了一种更为一般的计算工具.本文研究基于完备剩余格值逻辑自动机理论中的几个基本问题.　　 模糊有限自动机已经应用于设计复杂系统.对于一个最佳设计来说,关键是要找到模糊有限自动机的一个状态最小化形式.在经典自动机理论中,泵引理是验证某些语言为非正则语言的最基本、最有力的工具.因此.L-VFAs的状态最小化与L-值泵引理都具有重要的理论意义和实际价值.考虑到这些问题,本文有以下主要工作:　　 ·给出L-VFAs的一个扩展模型,即Mealy型L-VFAs(MLFAs),并讨论MLFAs的一些基本性质.　　 ·定义MLFAs的两种状态等价关系、状态约简及状态最小化,研究MLFAs的状态最小化形式的存在性,并证明任何两个可区分的状态都可以被某个具有有限长度的串所区分.另外,得到一个MLFAs的最小化算法,给出一个例子解释该算法.　　 ·考虑L-VFAs接受的L-值语言和L-值正则语言,证明L-值正则语言在并运算和交运算下是封闭的.给出L-值正则语言的一个新的泵引理,得到L-值语言正则性的一个充分必要条件.　　 模糊计算的形式化模型已经在计算模型的研究领域引起了广泛的关注.作为一个接受器,模糊Turing机具有比经典Turing机更强的计算能力.目前,有多种模糊Turing机模型被提出,并且得到了广泛而深入的研究.因此,本文试图建立基于完备剩余格值逻辑的Turing机理论的基本框架.本文的主要贡献在于研究了以下几个方面的内容:　　 ·给出L-值非确定型Turing机(L-NTMs)与L-值确定型Turing机(L-DTMs)的概念,并讨论L-值Turing机的一些相关性质.另外,证明多带L-NTMs与单带L-NTMs具有相同的语言识别能力.　　 ·介绍L-值递归可枚举语言与L-值递归语言,将分明语言的某些性质拓展到L-值语言;给出一些刻画递归可枚举语言、递归语言,以及n-递归可枚举语言的特征的相关结果.研究L-值Turing机的计算能力.另外,证明L-DTMs和L-NTMs在接受或判定语言时是不等价的.　　 ·证明通用L-值Turing机是不存在的.然而,若将完备的剩余格限定到一类更小的格,则通用L-值Turing机是存在的.