Context-sensitive immediate constituent analysis---context-free languages revisited

摘要

The ability of context-sensitive grammars to generate non-context-free languages is well-known. However, phrase structure rules are often used in both natural and artificial languages, not to generate sentences, but rather to analyze or parse given putative sentences. Linguistic arguments have been advanced that this is the more fruitful use of context-sensitive rules for natural languages, and that, further, it is the purported phrase-structure tree which is presented and analyzed, rather than merely the terminal string itself.

In this paper, a language is shown to be context-free if and only if there is a finite set of context-sensitive rules which parse this language; i.e., if and only if there is a collection of trees whose terminal strings are this language and a finite set of context-sensitive rules which analyze exactly these trees.