On the generating power of regularly controlled bidirection grammars

Asveld, P.R.J. and Hogendorp, J.A. (1991) On the generating power of regularly controlled bidirection grammars. International Journal of Computer Mathematics, 40 (1-2). pp. 75-91. ISSN 0020-7160

Preview

PDF
59Kb

Abstract:	RCB-grammars or regularly controlled bidirectional grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion. In addition, the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. In this paper the generating power of the derivation mode that uses right-occurrence rewriting (RO-mode) is determined. Furthermore, a new mode called RA is introduced, which is a better formalization of the intuitive idea of rightoccurrence rewriting than the RO-mode. The RO- and RA-mode have the same generating power, viz. the corresponding RCB-grammars both generate the recursively enumerable languages. Consequently, providing RCB/RO-grammars with a time bound results in a less powerful grammar model.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:	http://purl.utwente.nl/publications/17951
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 118470