摘要
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.
摘要译文
上下文敏感文法G据说是CS（K），当且仅当一种特殊表驱动的解析器，JK（G），existsCorresponding每个JK（G），我们定义一个类解析器JK（G）的JK（G）本身就是一个JK（G）的主要结果是：1Any处理器JK（G）的CS（K）文法G接受G2The一套可生成的语言在CS完全句子（ K）文法正好是确定性的线性有界自动机接受的语言集（DLBA的）3（a）为不可判定是否存在任意k铌0使得任意CSG是CS（K）（b）对于每一个固定ķ铌0，没有算法，将决定是否G是CS（k）和还构造JK（G），如果它exists4For任何DLBA MI算法被给予（ⅰ）构建的CS（ k）文法转基因，其产生由M接受的语言，以及（ii）构造一个处理器J1（GM）5CS（k）的文法的CS（k）文法的unambiguous6The句子可在解析时间成正比的推导的长度
Deterministic context-sensitive languages[C]//Switching and Automata Theory, 1969., IEEE Conference Record of 10th Annual Symposium on, 15-17 Oct. 1969, IEEE, 1969: 133-148