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...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.展开更多
In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed...In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains . It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described.展开更多
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69873042) .
文摘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.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69873042) .
文摘In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains . It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described.
