On the generating power of regularly controlled bidirectional grammars

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. Modifying the proof of our main result yields a characterization of the family NP of languages acceptable by nondeterministic Turing machines in polynomial time in terms of polynomially time-bounded RCB grammars.

Keywords:

• Controlled context-free grammar
• production and reduction (i.e. reversed production)
• mode of derivation
• recursively enumerable languages
• complexity classes

C.R. Categories:

• F.4.2
• F.4.3

^∗The work of the second author has been supported by the Netherlands Organization for Scientific Research (N.W.O.).

^∗The work of the second author has been supported by the Netherlands Organization for Scientific Research (N.W.O.).

Notes

^∗The work of the second author has been supported by the Netherlands Organization for Scientific Research (N.W.O.).