上下文有关语言

上下文无关规则只看待展开的一个非终结符；上下文有关规则可以同时检查它左右的符号。长度不缩短使推导到长度为 $n$ 的目标字时，无需先构造任意长的中间串再压回去。这一受控空间正是该语言类与线性有界自动机相连的原因。

“有关上下文”描述的是语言存在某种受限文法，而不是某个给定文法的表面写法。一个语言可能先由复杂文法呈现，却仍有更低层的等价描述；语言类别由是否存在相应模型决定。

语言

不是上下文无关语言，却是上下文有关语言。其文法或线性空间识别过程必须同步核对三段长度：可逐轮标记一个尚未处理的 $a$、对应的 $b$ 与对应的 $c$，并拒绝次序错误或数量不等的输入。整个过程只重写输入带上的有限标记，不需要超过线性长度的存储。

长度条件控制了中间推导的空间。若无条件允许 $A\to \epsilon$ 一类收缩规则，一般中间串可以先增长再任意收缩，文法的表达能力会越过本类限制。另一方面，“context-sensitive”不要求每条规则的左右都出现非空上下文；只要整个文法满足等价的非收缩约束即可。

空字约定必须单独固定。禁止所有收缩规则时，非空开始串不可能生成 $\epsilon$；允许受控的 $S\to \epsilon$ 后，又必须阻止 $S$ 出现在右侧，以免这条例外嵌入推导中反复造成收缩。Immerman–Szelepcsényi 定理还给出 CSL 对补运算封闭。

正则语言理路正则语言Regular language存在有限状态识别器的有限字语言，也就是只需固定有限种前缀摘要即可判断的语言。和上下文无关语言都包含在 CSL 中；包含均为严格。CSL 又严格包含于可判定语言理路可判定语言Decidability · Recursive language · Decidable language存在统一、总能停机且正确回答成员资格的判定器；等价于语言及其补语言都可识别。。它适合表达多个远距离数量约束、对称复制和受线性工作空间控制的语法条件，但“比 CFG 强”不代表存在统一高效解析器。

CSL 的非收缩文法定义与线性有界自动机理路线性有界自动机Linear-bounded automaton · LBA工作带可访问区域被输入长度的常数倍限制的非确定性图灵机。的精确对应、空字约定及双向构造见CSL–LBA 等价定理理路CSL–LBA 等价定理CSL-LBA equivalence · Kuroda theorem上下文有关语言恰为非确定性线性有界自动机接受的语言。。空间观点还把该语言类放入空间复杂度理路空间复杂度Space complexity计算在输入长度函数下使用的工作存储单元数量。的框架：非确定性线性空间足以识别它，而补封闭来自更深的空间复杂度结论。