Grammars, derivation modes and properties of indexed and type-0 languages (Q1098316)

The authors introduce an extension of a context-free grammar which in addition to the usual context-free productions \(A\to \alpha\) can contain also so-called index productions of the form Af\(\to B\) and \(A\to Bf\), where A and B are nonterminals and f belongs to a given set of indices. With these indices it is possible to distribute the information over context-free productions. It is shown in the paper that the so-called V-mode of derivation yields exactly the class of indexed languages and R-mode, respectively, the class of type-0 languages. A normal-form transformation, similar to the Chomsky normal form, is carried out. Moreover, using the notion of a generalized Dyck grammar, the authors give new homomorphic characterizations for indexed languages and type-0 languages.