Generalized context‐free grammars and multiple context‐free grammars
Tadao Kasami, Hiroyuki Seki, Mamoru Fujii · Systems and Computers in Japan · 1989
Abstract It is shown that the class of languages generated by generalized context‐free grammars (gcfg's) introduced by Pollard is exactly the class of recursively enumerable sets. Next, a subclass of gcfg's called multiple context‐free grammars (mcfg's) is introduced and it is shown that the class of languages generated by mcfg's properly contains the class of context‐free languages and is properly contained in the class of context‐sensitive languages. In mcfg's, it is possible to account for structures involving discontinuous constituents in a particularly simple manner. Such concepts as phrase structure and derivation tree in context‐free grammars (cfg's) can be extended naturally in mcfg's. Furthermore, the class of languages generated by mcfg's enjoys the formal language‐theoretic closure properties that the class of context‐free languages does.