中国科学F辑(英文版)
中國科學F輯(英文版)
중국과학F집(영문판)
SCIENCE IN CHINA(Series F)
2002年
1期
25-39
,共15页
CFRF%CFPRF%recursive functions of context free languages%CFL hierarchy enumeration%structure induction
It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non_numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed.