Generalized contextfree grammar
Generalized contextfree grammar (GCFG) is a grammar formalism that expands on contextfree grammars by adding potentially noncontext free composition functions to rewrite rules.^{[1]} Head grammar (and its weak equivalents) is an instance of such a GCFG which is known to be especially adept at handling a wide variety of nonCF properties of natural language.
Contents
Description[edit]
A GCFG consists of two components: a set of composition functions that combine string tuples, and a set of rewrite rules. The composition functions all have the form , where is either a single string tuple, or some use of a (potentially different) composition function which reduces to a string tuple. Rewrite rules look like , where , , ... are string tuples or nonterminal symbols.
The rewrite semantics of GCFGs is fairly straightforward. An occurrence of a nonterminal symbol is rewritten using rewrite rules as in a contextfree grammar, eventually yielding just compositions (composition functions applied to string tuples or other compositions). The composition functions are then applied, successively reducing the tuples to a single tuple.
Example[edit]
A simple translation of a contextfree grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language , where is the string reverse of , we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

(1)

(2a)

(2b)
The CF production of abbbba is
 S
 aSa
 abSba
 abbSbba
 abbbba
and the corresponding GCFG production is
Linear Contextfree Rewriting Systems (LCFRSs)[edit]
Weir (1988)^{[1]} describes two properties of composition functions, linearity and regularity. A function defined as is linear if and only if each variable appears at most once on either side of the =, making linear but not . A function defined as is regular if the left hand side and right hand side have exactly the same variables, making regular but not or .
A grammar in which all composition functions are both linear and regular is called a Linear Contextfree Rewriting System (LCFRS). LCFRS is a proper subclass of the GCFGs, i.e. it has strictly less computational power than the GCFGs as a whole.
On the other hand, LCFRSs are strictly more expressive than linearindexed grammars and their weakly equivalent variant tree adjoining grammars (TAGs).^{[2]} Head grammar is another example of an LCFRS that is strictly less powerful than the class of LCFRSs as a whole.
LCFRS are weakly equivalent to (setlocal) multicomponent TAGs (MCTAGs) and also with multiple contextfree grammar (MCFGs [1]).^{[3]} and minimalist grammars (MGs). The languages generated by LCFRS (and their weakly equivalents) can be parsed in polynomial time.^{[4]}
See also[edit]
References[edit]
 ^ ^{a} ^{b} Weir, David Jeremy (Sep 1988). Characterizing mildly contextsensitive grammar formalisms (PDF) (Ph.D.). Paper. AAI8908403. University of Pennsylvania Ann Arbor.
 ^ Laura Kallmeyer (2010). Parsing Beyond ContextFree Grammars. Springer Science & Business Media. p. 33. ISBN 9783642148460.
 ^ Laura Kallmeyer (2010). Parsing Beyond ContextFree Grammars. Springer Science & Business Media. p. 3536. ISBN 9783642148460.
 ^ Johan F.A.K. van Benthem; Alice ter Meulen (2010). Handbook of Logic and Language (2nd ed.). Elsevier. p. 404. ISBN 9780444537270.