On multiple context-free grammars (Q1177161)

This paper discusses some generalizations of context free grammars. The resulting languages lie between the class of context free languages and the class of context sensitive languages. The paper investigates and establishes containment relations, many of them strict, between the newly introduced classes of languages. The new classes of languages are known as \(m\)-parallel multiple context free languages (\(m-PMCFL\)) and \(m\)-multiple context free languages (\(m- MFCL\)), where \(m\) is a natural number parameter. For example, the class \(1-MCFL\) is identical to the class of context free languages; \(\{a^{2^ n}n\geq 0\}\) is a \(1-PMCFL\), and \(\{a^{n^ 2}n>0\}\) is a \(2-PMCFL\). The paper gives the containment relation \(m-MCFL\subset m- PMCFL\) and the strict containment relation \(m-MCFL\subset (m+1)-MCFL\). In addition, considering the classes \(PMCFL=\cup_ mm-PMCFL\) and \(MCFL=\cup_ mm-MCFL\), the paper proves that \(MCFL\) is properly contained in \(PMCFL\), which itself is properly contained in the class of context sensitive languages. Also, all the above classes are substitution-closed full AFLs. The paper contains an extensive development of these language classes, including algorithms for testing membership, a pumping lemma, and analyses of derivations. It also considers two classes of grammars previously considered by other authors - head grammars (hgs) and tree adjoining grammars (tags) - and relates them to the currently considered classes.