偶线性语言的有限双边可微性及其 Pumping 引理

Ehrenfeucht 等人在[1]中对正则语言的 Pumping 性质进行了讨论,他们给出了一个与正则性等价的 Pumping 性质,且提出了在上下文无关语言中建立一个类似定理的Open 问题。本文就一真包含正则语言类的上下文无关语言类子类——偶线性语言类给出了回答。定义1.一个偶线性文法是一个线性文法 G=(V,∑,P,S),其中生成式都具有     

基于完备剩余格值逻辑的下推自动机与上下文无关文法

引入了L-值下推自动机的概念,讨论了L-值下推自动机按2种不同方式所接受的语言类的等价性,并指出了它能识别L-值正则语言。利用广义的子集构造方法,证明了一般的L-值下推自动机与状态转移为分明函数且具有L-值终态的L-值下推自动机的等价性。通过此等价性,给出了L-值上下文无关语言的代数刻画和层次刻画,并证明了L-值上下文无关语言关于正则运算的封闭性。另外,提出了L-值上下文无关文法的概念,给出了与之等价的且带有经典开始符的L-值上下文无关文法。借此等价关系,讨论了L-值下推自动机与L-值上下文无关文法是等价的,并说明了在完备剩余格值逻辑意义下,可采用最左派生、最右派生、Chomsky范式或者Greibach范式中的任何一种来生成L-值上下文无关语言。     

应用模块法杂凑语言的上下文无关文法

编译程序的编制过程中,人们首先接触是语言,而上下文无关文法是作为程序设计语言重要的语法描述工具。因此,只有将语言用上下文无关文法表示才能使用现有的技术,从而用计算机自动实现。通过应用模块法将语言进行模块化划分,并在模块内实现杂凑,能够成功地、方便地实现语言到上下文无关文法的转换。     

Fuzzy上下文无关文法与Fuzzy上下文无关语言的性质

Ｆｕｚｚｙ下推自动机与Ｆｕｚｚｙ上下文无关文法有紧密的关系,讨论了Ｆｕｚｚｙ上下文无关文法及其产生Ｆｕｚｚｙ上下文无关语言的一些性质。     

Fuzzy下推自动机与Fuzzy上下文无关语言的关系

在文献基础上,讨论了Ｆｕｚｚｙ下推自动机按两种不同方式所接受的语言类的等价性,进而研究了Ｆｕｚｚｙ下推自动机所产生的语言与Ｆｕｚｚｙ上下文无关语言的等价关系,并提供由Ｆｕｚｚｙ下推自动机构造Ｆｕｚｚｙ上下文无关文法的方法。     

形式语言的无穷次商

本文证明了无穷次商的下列性质:①上下文无关语言对上下文无关语言的无穷次商是否上下文无关的问题是不可解的。②上下文无关语言对正则集的无穷次商仍是上下文无关语言。③正则集对任意集的无穷次商仍是正则集。     

模糊上下文无关树文法

定义了模糊上下文无关树文法(PCFTG)，讨论了其构造性质，给出其分解定理及表现定理，进而讨论了由模糊上下文无关树文法生成的语言IO(Inside-out)，模糊IO树语言的封闭性．     

改进的上下文无关文法及其语法分析

针对一些语言的实际应用情况,对标准的上下文无关文法作了改进,将标准的上下文无关文法定义中的非终结符集合和终结符集合进行细化,使得单词推导和句子推导可以使用同一个过程,即词法分析和语法分析可以在同一个语法分析过程完成.还给出了改进后文法的分析算法及算法的时间复杂度分析,证明用这种改进的方法进行语言文法定义更直观、简洁,其分析算法的时间复杂度优于标准上下文无关文法的分析算法.     

改进的上下文无关文法及其语法分析

针对一些语言的实际应用情况，对标准的上下文无关文法作了改进，将标准的上下文无关文法定义中的非终结符集合和终结符集合进行细化，使得单词推导和句子推导可以使用同一个过程，即词法分析和语法分析可以在同一个语法分析过程完成．还给出了改进后文法的分析算法及算法的时间复杂度分析，证明用这种改进的方法进行语言文法定义更直观、简洁。其分析算法的时间复杂度优于标准上下文无关文法的分析算法．     

连接文法在并行环境下的语法分析和识别

连接文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算.连接文法比上下文无关文法具有更强的生成能力.通过对连接文法深入的分析,提出了一种在并行环境下的语法分析和识别算法,算法事实是以上下文无关文法并行识别算法为基础提出的.最后以实例详细描述了算法并行处理过程并验证其算法的可行性.     

对上下文无关文法中的非终止符的相似性和等价性的判定

通过对具体文法的分析 ,定义了上下文无关文法中非终止符的相似性概念 ,提出了判定算法 ,并证明 :若两个非终止符的相似性达到一定程度 ,那么它们必定等价。利用上述结论 ,最终得到了一个判断上下文无关文法语言相同的充分性条件     

基于LL(1)分析表的布尔文法语法分析算法

布尔文法是针对特定的形式语言提出的一种新的描述形式,文法以上下文无关文法为基础,在形式规则中加入集合论的相关运算。传统的LL算法只能处理上下文无关文法,通过对布尔文法深入的分析,提出了一种基于LL(1)分析表的布尔文法的语法分析算法。通过实例详细描述了算法处理的过程,验证算法的可行性和正确性。     

基于Earley算法的关联文法语法分析的并行处理

关联文法是上下文无关文法的扩展,是在形式规则中加入集合的交运算。该文法比上下文无关文法具有更强的生成能力。通过对该文法深入的分析,提出了一种在并行环境下基于Earley算法的语法分析和识别算法。通过实例描述了算法并行处理的过程,验证算法的可行性和正确性。     

广义Chomsky范式文法的逆导出

本文定义了上下文无关文法的广义Chomsky范式,并应用[3]中的结果,建立了广义Chomsky范式文法的导出(映照),进而,作为这一文法的一种分析,获得了这一文法的逆导出。     

Fuzzy 2型属性文法与Fuzzy属性下推自动机

讨论了２型属性文法与属性下推自动机的关系,进一步给出了Ｆｕｚｙ上下文无关属性文法与Ｆｕｚｙ属性下推自动机,并详细讨论了二者的关系,达到了自动识别Ｆｕｚｙ２型属性文法语言的目的     

一般上下文无关文法的一个分析算法

本文给出一般上下文无关文法的一个分析算法。该算法可以看成是LR分析算法的推广,它既是自底向上,又是从左到右。理论分析表明本算法对一般文法具有时间界O(n~3)这里n是输入句子的长度);对有界歧义文法时间界为O(n~2),而对LR文法时间界为O(n)。由于本算法是先将文法转换成分析表,然后用分析表来指导对句子的分析。因而在实际应用中本算法一般要比Earley算法快,另外本算法输出中包含输入句子的所有可能的分析,并且仅需一简单枚举就可从此输出中找出句子的一个分析。     

格值正则文法及其语言的性质

给出了(确定)格值正则文法与(确定)格值正则语言的定义．从一个新的角度，即文法的角度研究确定格值正则语言关于正则运算的封闭性，从而完善了格值正则语言的运算性质，并给出了格值正则文法与确定格值正则文法等价的条件．     

上下文无关格值词语言研究

文章在格半群意义下，提出基于词计算的上下文无关格值文法，证明由其生成的格值词语言关于并与连接运算封闭，及其与乔姆斯基范式文法等价．     

模糊上下文无关树文法的分解定理和表现定理

定义了模糊上下文无关树文法（FCFTG），讨论了其构造性质，给出了其分解定理及表现定理，从两个不同的角度，阐明了FCFTG与非模糊上下文无关树文法的代数结构之间的关系，提供了将FCFIG转化为普通文法问题的方法。     

一种基于词频歧义消解的通用中文分词法

歧义是在基于词典的分词方法中常见的问题,以往的基于词典的分词方法往往使用双向最大匹配法获得分词结果后,通过使用上下文信息来进行歧义消解,但是对于没有上下文信息的单独语料无法进行歧义消解。本文提出一种通用的基于词频的歧义消解法,该方法是与上下文无关的,能够消解没有上下文信息的语料切分后产生的歧义,扩大了歧义消解的应用范围,简化了歧义消解的处理过程。实验表明:文本方法与传统基于词典的分词算法相比,具有更强的适用性及更高的可用性。