上下文无关语言上的递归函数——I.CFPRF及CFRF的定义  

作　　者：董韫美[1] 

机构地区：[1]中国科学院软件研究所计算机科学开放研究实验室,北京100080

出　　处：《中国科学（E辑）》2002年第1期103-115,共13页Science in China(Series E)

基　　金：国家自然科学基金资助项目(批准号:69873042)

摘　　要：建立上下文无关语言（CFL）上的递归函数理论,在CFL上定义了函数类CFRF和它的真子类CFPRF,它们可用来十分直接地表述非数值加工算法.事实上它们分别就是上下文无关语言上的偏递归函数和原始递归函数.提出了证明CFPRF函数性质的结构归纳法,给出一种枚举CFL句子的方法,定义了极小算子.基于CFL句子枚举,提出了极小算子的求值方法.最后,讨论了以CFRF为理论基础的可执行规约语言的设计和实现原则.

关 键 词：CFRF CFPRF 上下文无关语言 递归函数 CFL分层枚举 结构归纳法 形式文法 可计算性理论 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]