推导可交换上下文无关语言

提出了推导可交换上下文无关语言及其文法,证明了正规语言类和有界上下文无关语言类都是推导可交换上下文无关语言类的子集,而推导可交换上下文无关语言类是上下文无关语言类的一个子集;定义了该类语言的α闭包等有关运算,给出了推导可交换上下文无关语言表达式,证明了推导可交换上下文无关文法、推导可交换上下文无关语言表达式之间的等价转换.

可交换上下文无关文法

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

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

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

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

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

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

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

上下文无关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引理以及它们之间的关系.

上下文无关语言的可重复序列及其性质

通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.

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

在文献 (JournalofUESTofChina ,1992 ,2 1( 2 ) :188～ 190 )基础上 ,讨论了Fuzzy下推自动机按两种不同方式所接受的语言类的等价性 ,进而研究了Fuzzy下推自动机所产生的语言与Fuzzy上下文无关语言的等价关系 。

Fuzzy派生树与Fuzzy上下文无关语言的关系

给出了Fuzzy派生树、Fuzzy派生子树及其结果等概念 ,讨论了Fuzzy派生树与Fuzzy上下文无关语言的关系 。

Lukasiewicz逻辑值上下文无关语言的代数刻画

提出了基于Lukasiewicz逻辑的下推自动机(l-VPDA)的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。

形式语言中的上下文无关和上下文相关

形式语言与自动机理论已成为计算机科学的理论基础；对于程序设计语言的说明和分析尤其重要。文中介绍了形式语言与自动机理论中的基本原理，给出了上下文无关文法、上下文相关文法及其相应语言的定义，讨论了它们之间的关系。

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

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

Fuzzy上下文无关语言的运算封闭性

讨论了Ｆｕｚｙ上下文无关语言的并、链接。

一种上下文无关语言语法树的存储模式及其应用

针对上下文无关语言的句子所对应的语法树G树的表示形式提出了一种关系数据库的存储形式.这种存储形式的优点是:表示形式一致;句子分析简单;语句执行速度快.这种存储形式作为一种上下文无关语言的中间语言的形式可以直接交付解释器(抽象机)执行.同时介绍基于这种表示形式的上下文无关句子的编辑器.编辑器是基于W eb的交互式语法制导生成方式实现的.这种表示与存储形式被用于一种描述过程性知识的函数式语言.

上下文无关语言的广义泵引理

通常的关于上下文无关语言的泵引理，常被用来证明某些特殊的语言不是上下文无关的语言，但这种论证方法对有些非上下文无关语言不能适用，本文介绍的广义泵引理推广了通常的泵引理，并能解决通常的泵引理所不能解决的问题，它相比于Ｏｇｄｅｎ引理，未增加新的关于特指位置的概念。有些书上把泵引理中述及的条件，误认为是某语言成为上下文无关语言的充分条件，本文指出由此而引起的错误。

浅议格值代数系统与格值上下文无关语言

引入格值语言及文法的概念,建立格值代数系统与格值上下文无关文法的转换法则,并证明二者的等价性.研究格值代数系统与格值上下文无关语言的关系,得到结论 :格值代数系统的强解的某个分量就是与该格值代数系统等价的格值上下文无关文法生成的格值上下文无关语言。

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

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

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

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

基于最小序句子的上下文无关语言句子枚举

形式规约获取系统SAQ和一些形式化验证系统中常常需要枚举上下文无关语言的句子 ,现有的枚举方法较少且效率较低 以上下文无关语言L(G)的最小序句子和最大序句子为基础 ,从最小序句子开始按照一定的顺序扫描字符串 ,直至扫描到最大序句子为止 ,对被扫描的字符串进行判断取舍 在扫描的过程中采用削减和前瞻策略 ,很大程度上减少了被扫描的字符串个数 ,可以取得较好的时空性能 实验数据表明 。

ω上下文无关语言和语言的附着之间的关系

文章研究了用重复集生成的ω语言和语言的附着之间的关系，指出并证明了上下文无关语言附着类是ω上下文无关语言类的真子类，正规语言附着类是ω正规语言类的真子类．