LFG generation produces context-free languages

This paper examines the generation problem for a certain linguistically relevant subclass of LFG grammars. Our main result is that the set of strings that such a grammar relates to a particular f-structure is a context-free language. This result obviously extends to other context-free based grammatical formalisms, such as PATR, and also to formalisms that permit a context-free skeleton to be extracted (perhaps some variants of HPSG). The proof is constructive: from the given f-structure a particular context-free grammar is created whose yield is the desired set of strings. Many existing generation strategies (top-down, bottom-up, head-driven) can be understood as alternative ways of avoiding the creation of useless context-free productions. Our result can be established for the more general class of LFG grammars, but that is beyond the scope of the present paper.