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

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

上下文无关语言句子的反向自然枚举

在测试基于复杂数据结构的程序时,需要用到上下文无关语言句子的枚举。基于上下文无关语言按推导树高度的分层构造,提出了句子的反向自然枚举算法。通过堆、层、簇和长方体将句子划分为有穷集合序列,该算法的时间效率为,是被枚举句子的长度。实验数据表明,该算法是高效的,且应用更加便利。

CFL句子计数和分层词典序枚举

通过按推导树高度对句子分层,建立了句子集合中的分层词典序,进而发展出一种基于文法的,依分层词典序的,CFL句子计数和枚举方法,获得句子枚举的多个高效算法,对于无二义CFG,首先提出一个基础算法N2L,时间复杂度为O(n·lg(n)),n是被枚举句子的长度．对N2L进行改造,得到两个算法TD和BU,时间复杂度均为O(n)．对任意CFG,利用其推导树文法为工具后,文法无二义的限制被去除．对于一般的CFG,不论是否二义文法,也得到了依分层词典序的,时间复杂度为O(n)的枚举算法,同时枚举出句子及其推导树．该文的结果,从正面圆满回答了D(?)m(?)si提出的未决问题,即是否有按词典序,时间复杂度为O(n)的枚举算法?以及是否时间复杂度仅依赖于文法结构,及被枚举字之前同样长度的字的个数?本文给出的解答甚至比原问题所期望的更好．