Back to University of Twente portal
On the Generating Power of Regularly Controlled Bidirectional Grammars
Asveld, Peter R.J. and Hogendorp, Jan Anne (1989) On the Generating Power of Regularly Controlled Bidirectional Grammars. [Report]
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 63Kb |
| 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 right-occurrence 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: | Report |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/66966 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page