Regularly Controlled Bidirectional Extended Linear Basic Grammars

摘要

The concept of bidirectional application of productions - i.e., using a production of a grammar as a reduction too - is studied with respect to regularly controlled extended linear basic (macro) grammars, provided with a restricted mode of derivation. So this new grammatical model is in essence equal to the regularly controlled bidirectional context-free grammars of another paper by the author in which the underlying context-free grammar is replaced by an extended linear basic grammar. Closure properties of the corresponding family of languages are established; viz. for the outside-in or OI-mode one obtains a full substitution-closed AFL, and for the inside out or IO-mode one obtains a full QAFL closed under deterministic substitution. The notion of bidirectionality gives rise to a dramatic increase of generating power; even under minor assumptions the OI(IO) instance of such grammars generate all OI-macro (IO-macro, respectively) languages. Furthermore, in case of free application of productions and reductions one obtains a generating capacity equal to the one of phrase-structure grammars.