Deterministic context-sensitive languages: Part I

A context-sensitive grammar G is said to be CS(k) iff a particular kind of table-driven parser, Tk(G), exists. Corresponding to each Tk(G), we define a class of parsers T¯k(G). Tk(G) is itself a T¯k(G). The main results are:1.Any processor T¯k(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 Tk(G) if it exists.4.For any DLBA M, algorithms are given to (i) construct a CS(k) grammar GM that generates the language accepted by M, and (ii) construct a processor T¯1(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