正规文法与有限自动机的等价构造

在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂.对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例.     

正规文法与有限自动机的等价性研究

通过证明正规文法和有限自动机之间的等价性定理,给出正规文法和有限自动机之间的等价构造方法。     

Fuzzy正规集合与Fuzzy右线性文法的关系

在文献[1]的基础上,对Fuzzy正规集合和Fuzzy右线性文法之间的关系作了进一步的探讨,证明了Fuzzy正规集合的右线性可表示性,为进一步研究Fuzzy正规集合与Fuzzy有限状态自动机的关系提供了一种新方法.     

正规树文法的产生式相交判定

在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定.基于正规树文法的产生式的构成特点,提出了基于自动机的相交判定算法.根据产生式的内容模型即正则表达式,构建相应自动机,判定两个自动机的交是否为空,该算法的时间复杂度为O( ‖ E1‖·‖ E2‖·|∑E1 ∪∑E2 |).实验结果表明,该算法运行正确且高效,可以应用到针对产生式不相交的正规树文法的XML类型检查中.     

基于属性文法的正规式到NFA的转换

用状态转换图分析正规式时需要考虑的情况比较多,容易造成疏漏。且这种方法需要递归进行,多次扫描正规式,效率不高。该文采用SLR分析加属性文法只需一遍扫描就可以将正规式转存为NFA,效率要高得多。     

基于形式描述方法的文法进化算法研究

本文应用基于形式文法的方法,结合计算机科学中新兴有效的进化计算优化方法,进行了文法进化算法的有效性探索。通过运用巴科斯描述文法的四元组,强调了BNF产生式的设计,充分利用遗传操作来优化求解问题。并以有机化合物的分解(以离解能适应值进行适应度评价)为例子进行了算法设计,通过适应度函数择优,复制、交换和突变操作获得了实验结果。经过对结果的分析比较证明了算法的有效性。可以说是文法进化算法的成功探索。     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

二元文法

在正规文法的基础上,通过增加一个约束变量集合,给出了二元文法的定义,证明了二元文法与袋自动机的等价性,定义了平衡推导、递增推导、递减推导和传递推导,证明了它们与不变重复序列、增重复序列、减重复序列和传递重复序列之间的关系,并且给出判定一个二元文法所产生语言（袋语言）分别是正规语言、上下文无关语言或上下文文有关语言的充分条件。     

格值树自动机与格值上下文无关树文法的等价性

本文将模糊树自动机和模糊上下文无关树文法的概念推广到格半群上。证明了在接受语言和生成语言的意义下,树自动机和上下文无关树文法是等价的。同时给出了构造正规形式的等价文法的方法。     

有限自动机代数及其算法

本文提出有限自动机代数及其算法,它对于用有限自动机识别句子是有意义的。     

使用概率规则文法评估人机界面可用性

提出一种在界面系统设计规约的基础上使用的可用性评估方法.首先使用有限状态自动机抽象界面系统设计,根据概率规则文法对有限状态自动机的状态转换概率进行预测;然后结合用户的熟练程度提出了界面可用性评估算法;最后讨论了一个手机界面的可用性计算实例.文中方法能够在界面系统生命周期的早期使用,以较早地对不同设计方案进行比较,降低开发风险.     

基于扩展的BNF文法的通用语法分析算法

本文介绍了如何用句法图来表示扩展的BNF文法(EBNF),给出一个将EBNF文法翻译成句法图算法,然后我们给出一个适用于各种过程性高级语言的通用语法分析算法,同时考虑了语法错误的恢复和语义子程序的嵌入。     

KMP算法在正则文法中的应用

KMP又被称作克努特——莫里斯——普拉特操作(简称KMP算法)它是一种模式匹配算法,这个算法的关键是根据给定的模式串W1,m,定义一个next函数。本文阐述了利用KMP算法的匹配思想,解决不包含莫字符串系列的正则文法,该正则文法主要是用在词法分析过程中找出程序中的错误的代码,且对应的自动机中无等价的状态。本文根据KMP、正则文法和自动机的定义和基本原理证明了此技术的可行性和正确性,为编译程序设计提供自动生成最小化正则文法的技术和实现程序以供参考。     

由正规式构造FA__Thompson方法的改进

本文对由正规表达式改造为有限自动机的方法——Thompson方法存在的问题进行了分析,并在此基础上,对Thompson方法进行了改造．大大地减少了有限自动机的状态数和￡边,提高了编译程序的工作效率。     

词法扫描器的生成器算法用C++实现

该词法扫描器的生成器算法模型实现了由正规式转化为NFA再转化到DFA,然后用DFA识别输入串是否符合正规式的过程。该算法用C++的类完全封装起来,实现了较好的安全性与透明性,并且与C++实现了无缝嵌入,避免了LEX中的二次编译。     

关系图文法及其应用

字符串文法不适于描述二维以上事物的特征，无法定义事物之间的复杂关系．本文提出了关系图的概念，对关系图的性质进行了研究．在此基础上提出了一种新的文法——关系图文法．该文法能够方便地抽象和概括二维以上复杂对象的特征，为分析和识别这些对象提供工具和方法，可以广泛应用于模式识别、高维文本分析和描述图示语言的语法等领域．为了使关系图文法实用化，本文还提出了相应的识别和匹配算法.     

一种基于文法演化自动拟合非线性数据的蜂群算法

将文法演化方法引入蜂群算法, 基于上下文文法定义多种数学函数, 提出了自动拟合非线性数据的蜂群算法BCGE, 并给出了通过基因截断、基因增补及利用领域知识加速BCGE的方法。基于文法演化的BCGE比基于文法规划的其他算法更为简洁, 且存储基因型所需的空间也远比其他算法存储语法树所需的空间少。通过五个测试函数的实验表明, BCGE能够有效地拟合非常复杂的非线性数据。     

基于文法分支覆盖的短句子生成算法

提出一种上下文无关文法的句子生成算法.对于给定文法,算法生成一个满足该文法分支覆盖准则的句子集.结合长度控制、冗余消除和句子集规模控制等策略,使得生成的句子较短、无冗余、句子集规模较小.考察了算法在基于文法的软件系统的测试数据生成方面的应用情况.实验结果表明,该算法生成的测试数据具有较强的程序揭错能力,并且能够帮助测试人员提高测试速度.     

基于图算法的二元组合文法分析

为解决二元组合文法(BCG)的算符优先计算分析中不能共享分析树空间的问题,并降低分析算法的空间花费以提高分析效率,提出了一种基于图算法的BCG分析方法。该方法以表格方式存储分析过程中产生的所有边,分析完成后根据边的跨度构造分析树,从而使边不再局限于某一特定分析树中,再根据BCG文法的特性实现分析过程中的剪枝。实验结果表明,该方法在花费的时间、产生边的数量和最终结果树的数量上都明显低于传统的图算法和基于算符优先的算法。     

右线性文法与有限自动机等价性的一个新证明

迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...