交换Fuzzy正则语言注记

在探讨形式语言的交换性质的基础上,提出了AbelianFuzzy正则语言的概念,探讨了AbelianFuzzy正则语言在并、交和补算子下的封闭性,并得到了Fuzzy正则语言是半交换的的几个等价条件.由于Fuzzy正则语言的交换性质是形式语言之中一种较好的性质,对它的研究将有助于Fuzzy正则语言的机器实现.

粗糙正则语言

从正则语言的代数结构出发,利用Rough集理论对正则语言进行了扩充。提出了下(上)粗糙正则语言的概念,并给出了它们存在的条件,以及和正则语言之间的关系。

稠密相对正则语言的一些性质

主要讨论了稠密相对正则语言的一些性质.相对于正则语言的pumping引理,给出了稠密相对正则语言的类似结论.继而证明了稠密相对正则语言都含有本原字.最后给出了稠密相对正则语言和极大码的一些联系.

正则语言的特征性质

通常的关于正则语言的泵引理实际上是刻划了某语言为正则语言的一个必要条件．本文通过修改这个必要条件，得到了关于正则语言的充分必要条件，又泵引理或广义泵引理所叙述的结果作为推论而得到．另外，我们叙述了几个强弱不同的充要条件，以便供不同的使用（作为必要条件来使用，应该是越强越好，但作为充分条件来使用，又应该是越弱越好）．

关于正则语言的泵引理

通常关于正则语言的泵引理，常被用来证明某些特殊的语言不是正则语言，但这种论证方法对有些非正则语言不能适用。本文介绍几个广义的泵引理，它们不仅可解决通常的泵引理所能解决的问题，也可解决通常泵引理不能解决的问题。

Fuzzy正则语言与Fuzzy正则文法的关系

通过对Fuzzy正则语言与Fuzzy正则文法的关系的讨论 ,得到了二者的等价关系 ,这是进一步研究Fuzzy正则语言与Fuzzy有限状态自动机的一个起点 .

关于Fuzzy正则语言的一些性质

在定义 Fuzzy正则语言、Fuzzy有理语言等的基础上 ,研究 Fuzzy正则语言相关的一些性质 ,得到 Fuzzy正则语言与 Fuzzy有理语言间的对应关系 ,对

（P^（1，1））和正则语言

本文利用模型论博奕理论的方法证明了（Ｐ１，１）能够刻画正则语言．由此我们得到结论：在有限的离散线性序上（Ｐ１，１）和Ｍｏｎａｄｉｃ二阶逻辑的刻画能力是一致的．

正则语言推断综述

正则语言推断研究从语言的有限信息出发,通过归纳和推理得出正则语言模型.该技术在信息抽取、软件工程、模式识别等领域应用广泛.本文首先阐明了语言的可学习性概念和推断结果的评价准则.然后从推理策略、数据结构、算法复杂性等方面,对被动、主动和基于神经网络的学习算法进行分类归纳与对比,梳理各流派的技术发展脉络.接着分析推断产生的三种泛化效应.最后指出当前研究中不足,对未来研究方向进行展望.

一种新的正则语言的判定方法

针对当前的一些正则语言的判断方法,本文指出了其中的不足之处,在右同余等概念的基础上,通过在语言的符号集中引入等价关系,提出了判断某一给定语言是否是正则语言的代数判定定理,并与原有方法进行了对比。

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。

量子无穷正则语言的代数性质

引入了量子Müller自动机和量子无穷正则语言的概念.注意到量子Müller自动机识别的量子无穷正则语言的像集总是有限的,借助语义分析方法和量子状态构造技术,研究了量子Müller自动机的代数刻画,即证明了任一量子Müller自动机与具有分明初状态和状态转移函数且具有量子终状态的量子Müller自动机是相互等价的;借此给出了量子无穷正则语言的代数描述和层次刻画,即任一量子无穷语言A是可识别的当且仅当A的像集有限且A可表示为有限个特殊量子无穷正则语言的并;作为应用,证明了即使量子逻辑本身缺少分配律,量子无穷正则语言关于正则运算仍然封闭.

有穷自动机状态极小化方法及正则语言判定优化

引入了等价性原则，定义等价关系的商集合互∑^＊／～B，通过对商集合的有限性判断，来判定正则语言，大大简化了正则语言判定的步骤，并在有穷自动机的状态集上引入了等价关系，对等价状态进行压缩，构造出与其等价的最小有穷自动机，同时降低了有穷自动机状态的复杂性．

Fuzzy正则语言的有限幂性质(II)

Fuzzy正则语言L具有有限幂性质的充分必要条件是集合 {Li|i=0 ,1,2 ,… }有限 .讨论了任意给定一个Fuzzy正则语言 。

关于ω-正则语言类的一个子类的特征

为了给出本文的主要结果,首先引进了由有穷字母表∑上的ω^-语言所确定的集合∑~ω上的ω-Nerode等价关系的概念.在此基础上证明了∑上的与前缀逆相关的ω^-语言是ω^-正则语言,当且仅当由它所确定的ω-Nerode等价关系的指数有穷.从而,本文从代数、集合的角度给出了在∑上的与前缀逆相关的一类ω^-语言中,ω^-正则语言的特征.

Fuzzy ω正则语言的注记

定义Σω上的ω-Nerode等价关系的符号,并且定义了Σ上Fuzzy前缀逆相关ω-语言和左逆封闭语言,在这些定义的基础上,得到了Σ上Fuzzy前缀逆相关ω-语言是Fuzzyω正则语言的充分必要条件是由L定义的ω-Nerode等价关系的指数有限,Σ上Fuzzyω正则语言可以表示成Σω上一些具有有限指数的左不变等价关系的某些等价类的并集。因而在由前缀逆相关ω-语言或左逆封闭ω语言组成的ω-语言类中,Fuzzyω正则语言的代数特征就可从代数和集合论的观点给出。这为进一步研究Fuzzy有限状态自动机和Fuzzy正则语言奠定了基础。

格值正则语言截集的逼近性质

主要在格半群L=[0,1]上研究了格值正则语言截集的逼近性质,从覆盖、拟正定等方面给出了格值正则语言的截集语言可被正则语言逼近的一些充分或必要条件.

关于正则语言的子集的研究

基于泵引理和正则语言的代数判定定理,本文证明了正则语言的子集未必是正则语言。以L={x|x∈{0,1}^*,且x中(10)和(10)作为子串出现次数相等}为例,文中通过构造等价语言L’={x|x∈{0,1}^*,且x的首尾字符相同}证明了L的正则性,其子集L2={01)^n(10)^n|n≥0}易通过泵引理证明不是正则语言。最后将结论推广到上下文无关语言中。

关于一个串为正则语言中某串的子串的判定算法

本文给出一个判定∑上的任意串s是否为一正则语言L中某个串的子串的算法,即设s为∑上的任一串,L是∑上的任一正则语言,则s为L中某个串的子串,当且仅当s为集合V_n={w∈∑|w∈L,|w|≤2n+k-2}中某串的子串,其中k=|s|,n是某个自然数。

正则语言的一个特征

Myhill-Nerode定理利用等价关系描述了正则语言的一个重要特征,它是有限自动机理论中的一个经典、优美的结果。为了将Myhill-Nerode定理推广到更一般的情形,引入了有限自动机M上的状态转移半群和Σ*上的M-半群,讨论了其若干性质。在此基础上,将Myhill-Nerode定理中的等价关系一般化,给出了正则语言的一个新的特征定理,Myhill-Nerode定理成为该定理的一个推论。讨论了正则语言的最一般的特征,提出了有待进一步研究的问题。