上下文有关语言

形式陈述 ​

非收缩文法沿用形式文法公理库形式文法Formal grammar · Generative grammar以终结符、非终结符、产生式和开始符号有限描述语言的通用生成系统。的四元组 $G=(V,\mathrm{\Sigma },R,S)$，但不把通用语法误接在更特殊的 CFG 之下。它的产生式可有一般形式

$$\alpha \to \beta ,$$

其中 $\alpha ,\beta \in (V\cup \mathrm{\Sigma }{)}^{\ast }$，$\alpha$ 至少含一个非终结符，并满足 $|\alpha |\le |\beta |$。若允许空字，通常额外准许 $S\to \epsilon$，同时要求开始符号 $S$ 不出现在任何产生式右侧。由某个这类文法生成的形式语言公理库形式语言Formal language · Language over an alphabet字母表上有限字符串集合的抽象，是自动机输入与计算问题编码的基本对象。称上下文有关语言，简称 CSL。

传统的上下文形式写作

$$\alpha A\beta \to \alpha \gamma \beta ,\gamma \ne \epsilon ,$$

表示只有当非终结符 $A$ 位于上下文 $\alpha ,\beta$ 之间时才可改写。传统形式与非收缩形式在生成的语言族意义下等价，但不是说每一条任意非收缩规则本身都已长成传统形式。

直觉 ​

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

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

例子与边界 ​

语言

$$L=\{a^n{b}^n{c}^n:n\ge 1\}$$

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

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

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

推论与应用 ​

正则语言公理库正则语言Regular language能被某个有限自动机识别的形式语言。和上下文无关语言都包含在 CSL 中；包含均为严格。CSL 又严格包含于可判定语言。它适合表达多个远距离数量约束、对称复制和受线性工作空间控制的语法条件，但“比 CFG 强”不代表存在统一高效解析器。

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

参考资料

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, Ch. 11.
• Sige-Yuki Kuroda, “Classes of Languages and Linear-Bounded Automata,” Information and Control 7 (1964), 207–223.
• Neil Immerman, “Nondeterministic Space is Closed Under Complementation,” SIAM Journal on Computing 17 (1988), 935–938.