On the Generating Power of Regularly Controlled Bidirectional Grammars

P.R.J. Asveld, J.A. Hogendorp, J.A. Hogendorp

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    56 Downloads (Pure)

    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.
    Original languageUndefined
    Pages (from-to)75-91
    Number of pages17
    JournalInternational journal of computer mathematics
    Volume0
    Issue number40
    Publication statusPublished - 1991

    Keywords

    • HMI-SLT: Speech and Language Technology
    • METIS-118470
    • EWI-9414
    • IR-17951

    Cite this

    Asveld, P. R. J., Hogendorp, J. A., & Hogendorp, J. A. (1991). On the Generating Power of Regularly Controlled Bidirectional Grammars. International journal of computer mathematics, 0(40), 75-91.