Abstract :
A context-sensitive grammar G is said to be CS(k) iff a particular kind of table-driven parser, Jk(G), exists. Corresponding to each Jk(G), we define a class of parsers Jk(G). Jk(G) is itself a Jk(G). The main results are: 1. Any processor Jk(G) for a CS(k) grammar G accepts exactly the sentences of G. 2. The set of languages generable by CS(k) grammars is exactly the set of languages accepted by deterministic linear-bounded automata (DLBA´s). 3. (a) It is undecidable whether there exists any k ≥ 0 such that an arbitrary CSG is CS(k). (b) For every fixed k ≥ 0, there is no algorithm that will decide if G is CS(k) and also construct Jk(G) if it exists. 4. For any DLBA MI algorithms are given to (i) construct a CS(k) grammar GM that generates the language accepted by M, and (ii) construct a processor J1 (GM). 5. CS(k) grammars are unambiguous. 6. The sentences of a CS(k) grammar can be parsed in a time proportional to the length of their derivations.
