CSL–LBA 等价定理

形式陈述 ​

固定空字的同一约定。对语言 $L\subseteq {\mathrm{\Sigma }}^{\ast }$，下列条件等价：

1. $L$ 由某个非收缩文法生成，即 $L$ 是上下文有关语言公理库上下文有关语言Context-sensitive language · CSL可由非收缩文法生成、允许产生式读取局部上下文的形式语言类。；
2. $L$ 被某台非确定性线性有界自动机公理库线性有界自动机Linear-bounded automaton · LBA工作带可访问区域被输入长度的常数倍限制的非确定性图灵机。接受。

若语言包含 $\epsilon$，文法侧允许受控规则 $S\to \epsilon$ 且 $S$ 不出现在任何右侧；机器侧单独规定空输入的接受。对非空字，两种模型都不需要这一例外。

证明纲要 ​

下面保留双向构造的关键编码与正确性理由，但不逐条列出机器到文法方向的全部局部产生式，因此是证明纲要而非完整形式构造。

文法到机器的构造如下。对长度为 $n$ 的输入 $w$，LBA 在其线性带区中从 $S$ 开始，非确定地选择产生式和出现位置，维护当前 sentential form，并拒绝任何长度超过 $n$ 的分支。因为文法不收缩，一条最终得到 $w$ 的推导中，所有中间串长度都不超过 $n$。机器接受当且仅当某个分支恰好生成 $w$。

机器到文法的构造把长度受限的配置编码为固定长度字符串，其中状态符号标记读写头位置。文法用长度保持或不减长规则模拟每个合法转移。为在结束时重新得到原输入，配置符号可同时携带初始输入符号与当前工作符号；只有进入合法接受配置后，清理阶段才把辅助标记改写为对应终结符。这样生成的终结字恰是被机器接受的输入。

直觉 ​

非收缩文法不能先把中间串任意拉长再压回目标，因此生成长度 $n$ 的字时，候选推导可在 $O(n)$ 个符号格内搜索。反过来，LBA 的整个瞬时状态——带内容、读写头和有限控制——也能编码进线性长度的串，并由局部文法规则逐步更新。

两边是同一空间限制的生成式与识别式表达：文法从开始符号向目标字生长，机器从目标字出发寻找一条接受计算。等价的关键是编码合法演化，而不是“二者看起来都只用线性长度”。

例子与边界 ​

语言

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

可由非收缩文法生成，也可由 LBA 在原输入上逐轮标记配对的 $a,b,c$。文法方向说明它属于 CSL，机器方向则把同步三个计数变成线性空间中的反复扫描。

证明不能只说“固定输入的配置数有限，所以文法与机器等价”。配置有限至多说明搜索可被判定；还必须给出语法规则如何保持合法配置、接受时如何输出原输入，以及反向模拟为何不超过目标长度。

经典定理使用非确定性 LBA。若把它未经说明换成确定性 LBA，就会触及确定性与非确定性线性空间是否相等的开放问题。多带、一带、端标记和常数倍带区的模型变体通常等价，但模拟时必须证明空间只增加常数因子。

空字也是实际边界。非收缩文法从非空开始符号无法生成空串，所以文法例外与机器的空输入行为必须同步；只在一侧“默认包含 $\epsilon$”会让定理差一个语言。

推论与应用 ​

该定理给Chomsky 层级公理库Chomsky 层级Chomsky hierarchy按产生式限制排列正则、上下文无关、上下文有关与递归可枚举语言，并由典型语言证明严格包含。的 Type 1 层提供机器刻画。它还说明每个 CSL 都可判定：固定输入下 LBA 只有有限多个配置，可在配置图中判断接受配置是否可达，即使直接的非确定搜索可能循环。

从复杂度角度看，CSL 对应非确定性线性空间。补封闭并非从文法定义显然得到，而是依靠 Immerman–Szelepcsényi 定理。机器刻画因此不仅重述语言类，还把文法性质连接到空间复杂度与配置图可达性。

参考资料

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