Controlled bidirectional grammars

Abstract

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We distinguish several modes of derivation for this kind of grammar. The resulting language families (properly) extend the family of context-free languages. We establish some closure properties of these language families and some grammatical transformations which yield a few normal forms for this type of grammar. Finally, we consider some special cases (viz. the context-free grammar is linear or left-linear), and generalizations, in particular, the use of arbitrary rather than regular control languages.

Keywords:

• Controlled context-free grammar
• production and reduction (i.e. reversed production)
• mode of derivation
• normal form
• closure properties

C.R. Categories:

• F.4.2
• F.4.3

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

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

Notes

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