| Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions |
| |
| 引用本文： | 董韫美.Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions[J].中国科学F辑(英文版),2002,45(2). |
| |
| 作者姓名： | 董韫美 |
| |
| 作者单位： | DONG YunmeiLaboratory of Computer Science，Institute of Software，Chinese Academy of Sciences，Beijing 100080，China |
| |
| 基金项目： | 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.
|
Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions |
| |
| DONG YunmeiLaboratory of Computer Science.Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions[J].Science in China(Information Sciences),2002,45(2). |
| |
| Authors: | DONG YunmeiLaboratory of Computer Science |
| |
| Affiliation: | Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China |
| |
| Abstract: | 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. |
| |
| Keywords: | CFRF CFPRF recursive functions of context free languages bounded operators |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
