基于量子逻辑的下推自动机与上下文无关文法

给出基于量子逻辑的下推自动机(l-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的l-VPDA与状态转移为分明函数且具有量子终态的l-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(l-VCFG)的等价性.

广义有界上下文无关语言与Petri网语言

提出了广义有界上下文无关语言的概念,该类语言是上下文无关语言的真子集;证明了广义有界上下文无关语言与上下文无关Petri网语言的等价性;进一步给出了上下文无关Petri网语言的一种形式描述--上下文无关Petri网语言表达式,对上下文无关Petri网语言给出了较完整的结构特征.

可交换上下文无关文法

本文提出了可交换上下文无关文法及其该文法产生的语言——可交换上下文无关语言,证明了正规语言类是可交换上下文无关语言类的一个子集,而可交换上下文无关语言类是上下文无关语言类的一个子集;讨论了可交换上下文无关语言的结构特点,并给出了可交换上下文无关语言的Pumping引理。

量子上下文无关文法的代数性质

提出了量子上下文无关文法(l-VCFG)的概念,并研究了其具有的代数性质;证明了量子上下文无关文法(l-VCFG)和Chomsky范式文法(l-VCNF)以及Greibach范式文法(l-VGNF)的相互等价性;详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。

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

:Fuzzy下推自动机与Fuzzy上下文无关文法有紧密的关系 .

格值上下文无关文法的代数刻画

在格值逻辑框架下给出上下文无关文法及上下文无关语言的概念,给出格值逻辑意义下广义的格值子集构造方法,并证明了任一与除一步推导为格值以外,其余推导都是经典推导的之间的相互等价性。

格值上下文无关语言的运算性质

在格值逻辑框架下给出上下文无关文法及上下文无关语言的概念,并研究了格值上下文无关语言在正则运算下的封闭性。

面向上下文无关语言的测试工具的设计和实现

软件测试是软件开发生命周期的重要组成部分 ,也是目前和今后相当长一段时间内保证软件质量和可靠性的主要手段 .首先以两个已经实现了的分别面向 VB和 C/ C+ +语言的计算机辅助软件测试工具为基础 ,将该系列测试工具的系统结构推广至适用于任何一种上下文无关语言 .而该系列测试工具高度的模块可重用性特征为这种推广提供了必要的基础 .为实现这种高度的模块可重用性特征 ,从各个角度论述了增强该特征的设计 ,提出了基于块的程序划分机制 .这种机制从根本上保证了对多种上下文无关语言的测试语义的一致性 .最后 ,还给出了两个不同语言写就的实例的运行结果 ,以说明这种一致性 .

量化上下文无关语言的代数性质

通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。

一种基于概率上下文无关文法的汉语句法分析

本文研究了PCFG独立性假设的局限性,并针对这一局限性提出了句法结构共现的概念以引入上下文信息,给出了计算方法;为了打破中文树库规模过小的局限性,对于句法规则参数的获取,本文利用In-side-Outside算法进行迭代,最后提出了一个基于统计模型的自顶向下的汉语句法分析器。在封闭测试下,其标记精确率和标记召回率分别为88.1%和86.8%。实验结果表明,这种方法确实能够提高标记的精确率和召回率,值得深入研究。

上下文无关语言分析树的一种表示形式

介绍了上下文无关语言 (CFL)的句子的一种分析树表示 ,它适合用于一类与以往不同的 CFL 的应用 ,即对分析树空间效率要求较高且不需标记分析树的应用 ,典型的就是把 CFL的句子用作算法加工对象 .这种表示比传统分析树不仅空间较小 ,而且进行结构匹配的速度快 .还介绍了这种分析树表示的实现技术 .

上下文无关文法测试充分性

讨论了文法测试的基本概念 ,分析了文法测试的特点、应用场景及其与一般软件测试的异同 .形式化地定义了上下文无关文法的测试充分性准则 ,提出了一个上下文无关文法的测试充分性准则族 .分析了该准则族中各准则之间的包含关系 ,以及这种包含关系与揭示文法所特有的 2类缺陷的能力之间的关系 .计算和比较了准则族中各准则的测试集规模复杂性 .为了评价文法的测试开销 ,定义了一个上下文无关文法的测试复杂性度量 ,该度量能够从测试充分性的角度反映测试一个文法的难易程度和测试开销的大小 .

面向上下文无关语言的信息提取模块化设计

为实现白盒测试的源文件信息提取,提出了通过Lex和Yacc对使用上下文无关文法定义的语言进行词法和语法分析,构建独立的信息提取模块的思想。在函数信息提取部分提出了块和级的概念,用语句结构和语句链表结构将函数定义信息表示出来。在类信息提取部分通过识别出类声明中的成员变量和成员函数的声明信息,建立成员链表结构;识别类声明信息,建立类结构。然后将这些结构信息存入数据库,以供后续模块使用,充分做到了模块独立性和可重用性。这样只需要设计不同的信息提取模块,就可以将目前已经实现的面向C/C++语言的软件测试工具WBoxTool推广应用到其它面向上下文无关文法的语言。

上下文无关Petri网语言的Pumping引理

Petri网语言可分为正规Petri网语言、上下文无关Petri网语言和Petri网语言三类,Pumping引理反映了一类语言的共性.对于正规Petri网语言类和Petri网语言类都已给出了其相应的Pumping引理,而对于上下文无关Petri网语言类的Pumping引理却一直未给出.本文通过分析上下文无关Petri网语言的结构性质,给出了上下文无关Petri网语言的Pumping引理,并且正规Petri网语言的Pumping引理是上下文无关Petri网语言的Pumping引理的一种特殊形式,而上下文无关Petri网语言的Pump-ing引理又是Petri网语言Pumping引理的一种特殊形式,从而完整地解决了三类Petri网语言Pumping引理以及它们之间的关系.

用待确定的上下文无关文法分析半结构化数据

对上下文无关文法作了改进，改进后的方法能在语法分析的过程中利用已分析部分的语义信息，得出待分析部分未确定的语法结构，使其可用于处理复杂的半结构化数据．

格值下推自动机与格值上下文无关文法

引入了格值下推自动机、格值上下文无关文法及它们的语言的概念,证明了格值下推自动机以两种不同方式接受的语言类的等价性,研究了格值Chomsky范式文法、格值上下文无关文法及其派生所产生的语言的等价条件,揭示了在一定条件下,格值下推自动机接受的语言类与格值上下文无关文法产生的语言类的等价性,证明了有理格值语言均被格值下推自动机识别。

逐步求精法获取上下文无关文法

文法推断研究如何从语言的有限实例，通过归纳推断获取语言的文法定义． 文中提出一个基于逐步求精的上下文无关文法推断方法，以尝试将文法推断用于替代或帮助传统手工的文法构造工作． 文中的推断方法以Ａｎｇｌｕｉｎ 的交互式学习模型为框架，以逐步求精和复用为主要策略。

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

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

用上下文无关语法来描述汉字结构

上下文无关语法(简称CFG)在自然语言的句法自动分析中已经得到广泛的应用。本文使用CFG来分析和描写汉字的结构,以部件作为汉字结构的枢纽,把汉字部件的11种结构方式看成CFG中的非终极符号,把末级部件看成CFG中的终极符号,使用树形图及其等价的括号表达式成功地对汉字的结构进行了形式描述。

上下文无关文法与藏语句法分析

上下文无关文法在计算机句法自动剖析中已经得到广泛的应用。文章利用这种上下文无关文法来分析和描写藏语句子结构,在句法分析过程中具体采纳预测和规约的分析方法,以举例验证的方式自动推导出藏语句子的句法结构规律;识别句子中的句法单位,以及各句法单位之间的关系,对藏文句法分析提供了较好的研究思路及探索价值。