|
|||||
|
|
A simultaneous reduction of several measures of descriptional complexity in scattered context grammars |
|
| Authors: | H. Fernau |
| Affiliation: | a University of Newcastle, School of Electrical Engineering and Computer Science, University Drive, NSW 2308 Callaghan, Australia b Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Bo?etěchova 2, Brno 612 66, Czech Republic |
| Abstract: | In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions. |
| Keywords: | Formal languages Scattered context grammars Reduction Context sensitive productions |
| 本文献已被 ScienceDirect 等数据库收录！ | |