ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The ability of context-sensitive grammars togenerate 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 toanalyze or parse given putative sentences. Linguistic arguments have been advanced that this is the more fruitful use of CS rules for natural languages, and that, further, it is the purported phrasestructure tree which is presented and analyzed, rather than merely the terminal string itself. In this interpretation, for example the rules {S → AB, A → a/__b, B → b/ a__} “parse” the sentenceab for they “analyze” the tree represented by the labeled bracketing [S[Aa]A[Bb]B]S, even though these rules do not generateab when interpreted as a CS grammar. We shall say that a languageL is parsed by the finite setR of context-sensitive rules ifL consists of the terminal strings of trees analyzed byR. An actual parsing of an artificial language might be obtained, for example, by using a standard “parsing algorithm” for the associated CF grammar (obtained by deleting all contexts from rules) to generate putative trees and then analyzing these trees with the given CS grammar. In this paper, a language is shown to becontext-free if and only if there is a finite set ofcontext-sensitive rules which parse this language; i.e., if and only if there is a collection of trees whose terminal strings are the sentences of this language and a finite set of CS rules which analyze exactly these trees.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01740724
Permalink
