论文部分内容阅读
树自动机是接收树形式语言的数学模型,是传统字符自动机(词自动机)的拓展和推广。传统的树自动机不仅是复杂理论的基础,而且在学习系统、模式识别和数据库理论等诸多领域都有着广泛的应用。为解决连续空间或具有不确定性(模糊)信息的系统问题,模糊树自动机应运而生。模糊树自动机的同余与同态、等价性以及最小化等问题都有了一些研究成果。模糊集代数是研究模糊树自动机的理论基础,不同定义的模糊集代数将定义出不同类型的模糊树自动机,因此本文首先将研究重点放在了模糊集代数上。模糊树语言的产生体系形式不一,为说明不同模糊树语言产生体系的等价性,构建标准化的产生体系模型就显得尤为重要,所以本文研究了模糊树语言产生体系的正则形式。语言的封闭性问题在模糊自动机理论的研究中已有触及,即模糊语言的封闭性,本文中则对模糊树语言的封闭性展开了研究,进一步完善了语言的封闭性问题。本文的工作主要涵盖以下三个方面:1.最小乘积模糊集代数:在项代数上定义最小乘积模糊集代数,通过归纳假设方法证明了一类特定形式n元树的性质满足最小乘积模糊集代数形式。进而说明了在项代数上成立的线性正规等式在格值模糊集上也成立,表明了线性正规等式下的等价类的封闭性。最后证明了该模糊集代数满足分配律且具有保序性。2.F-CFDS的正则形式:在梳理树和伪项、模糊上下文无关树型语言产生体系(F-CFDS)以及模糊上下文无关树型语言(F-CFDL)概念基础上,证明了对任意n阶F-CFDS,存在n-1阶的等价F-CFDS,以此阐明对任意F-CFDS都存在1阶的等价F-CFDS,给出了这类F-CFDS的正则形式,并举例进行了说明。3.模糊树语言的封闭性:讨论了模糊树自动机、模糊上下文无关树型语言与模糊上下文无关文法的推导树集三者之间的对应关系。在模糊树自动机语言上定义了并、交、连接和Kleene闭包运算,给出了Kleene闭包运算的一个等价性条件,证明了模糊树自动机语言在上述定义的四种运算下是封闭的。