Nonterminal complexity of one-sided random context grammars |
| |
Authors: | Alexander Meduna Petr Zemek |
| |
Affiliation: | 1.Department of Information Systems, Faculty of Information Technology, IT4Innovations Centre of Excellence,Brno University of Technology,Brno,Czech Republic |
| |
Abstract: | In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove
that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals.
An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules
coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert
any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random
context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|