上下文相关语法可以有一个空字符串吗？
Can a context-sensitive grammar have an empty string?
在我的一个cs 类中，他们提到上下文无关文法和上下文相关文法之间的区别在于，在CSG中，生产规则的左侧必须小于或等于右侧。
所以，他们给出的一个例子是上下文相关语法不能有空字符串，因为这样就不会满足第一条规则。
不过，我了解到常规文法包含在上下文无关中，上下文无关包含在上下文相关中，上下文相关包含在递归可枚举文法中。
因此，例如，如果文法是递归可枚举的，那么它也是上下文相关的、上下文无关的和常规的类型。
问题是，如果发生这种情况，那么如果我有一个包含空字符串的上下文无关文法，那么它将不满足被算作上下文相关的规则，但是矛盾会发生，因为每个上下文相关的都是上下文无关的。
空产生式（“lambda 产生式”，之所以这样称呼是因为 λ 通常用于指代空字符串）可以从任何上下文无关语法中机械地消除，除了可能的顶级产生式 S → λ.这样做的算法在形式语言理论的每一篇文章中都有很好的介绍。
因此，对于任何具有 lambda 产生式的 CFG，都有一个等效的没有 lambda 产生式的 CFG，它生成相同的语言，也是上下文相关的语法。因此，CSG 中对合同规则的禁止不会影响 语言 的层次结构：任何上下文无关的 语言 都是上下文敏感的 语言.
乔姆斯基最初对上下文相关文法的定义并没有指定非契约式 属性，而是一个更具限制性的文法：每个产生式都必须采用 αAβ→αγβ 形式，其中 A 是单个符号， γ 不是空的。这组文法生成与非契约文法相同的语言集（乔姆斯基也证明了这一点），但它不是同一组。此外，他的上下文无关文法确实是上下文相关文法的一个子集，因为根据他对 CFG 的最初定义，lambda 产生式是被禁止的。 （1959 年的论文可在线获取；请参阅 Wikipedia article on the Chomsky hierarchy 以获取参考 link。）
正是非空上下文的存在——α和β——导致了名称“上下文敏感”和“上下文无关”；对于诸如 AB→BA 之类的任意非合同规则，“上下文敏感”可能意味着什么还不太清楚。 (注一)
简而言之，鉴于您在问题中引用的 CFG 和 CSG 的现代常见用法，“每个 CFG 都是 CSG”的说法在技术上是不正确的。但这只是一个技术问题：带有 lambda 产生式的 CFG 可以被机械地转换，就像一个非收缩语法可以被机械地转换成一个符合乔姆斯基定义的上下文相关的语法（参见 Wikipedia article on non-contracting grammars）。
（通过向 CFG 和 CSG 定义添加规则 S→λ 的例外，允许上下文相关和上下文无关语言都包含空字符串也很常见。）
备注
- 在乔姆斯基对上下文无关和敏感语法的表述中，解析树的含义是明确的，即使对于 CSG 也是如此；由于乔姆斯基是一位语言学家，并且正在寻找一个框架来解释自然语言的结构，因此解析树的概念很重要。您如何将
AB → BA 的结果描述为解析树一点也不明显，尽管在 a A b → B. 的情况下很清楚
在我的一个cs 类中，他们提到上下文无关文法和上下文相关文法之间的区别在于，在CSG中，生产规则的左侧必须小于或等于右侧。
所以，他们给出的一个例子是上下文相关语法不能有空字符串，因为这样就不会满足第一条规则。
不过，我了解到常规文法包含在上下文无关中，上下文无关包含在上下文相关中，上下文相关包含在递归可枚举文法中。
因此，例如，如果文法是递归可枚举的，那么它也是上下文相关的、上下文无关的和常规的类型。
问题是，如果发生这种情况，那么如果我有一个包含空字符串的上下文无关文法，那么它将不满足被算作上下文相关的规则，但是矛盾会发生，因为每个上下文相关的都是上下文无关的。
空产生式（“lambda 产生式”，之所以这样称呼是因为 λ 通常用于指代空字符串）可以从任何上下文无关语法中机械地消除，除了可能的顶级产生式 S → λ.这样做的算法在形式语言理论的每一篇文章中都有很好的介绍。
因此，对于任何具有 lambda 产生式的 CFG，都有一个等效的没有 lambda 产生式的 CFG，它生成相同的语言，也是上下文相关的语法。因此，CSG 中对合同规则的禁止不会影响 语言 的层次结构：任何上下文无关的 语言 都是上下文敏感的 语言.
乔姆斯基最初对上下文相关文法的定义并没有指定非契约式 属性，而是一个更具限制性的文法：每个产生式都必须采用 αAβ→αγβ 形式，其中 A 是单个符号， γ 不是空的。这组文法生成与非契约文法相同的语言集（乔姆斯基也证明了这一点），但它不是同一组。此外，他的上下文无关文法确实是上下文相关文法的一个子集，因为根据他对 CFG 的最初定义，lambda 产生式是被禁止的。 （1959 年的论文可在线获取；请参阅 Wikipedia article on the Chomsky hierarchy 以获取参考 link。）
正是非空上下文的存在——α和β——导致了名称“上下文敏感”和“上下文无关”；对于诸如 AB→BA 之类的任意非合同规则，“上下文敏感”可能意味着什么还不太清楚。 (注一)
简而言之，鉴于您在问题中引用的 CFG 和 CSG 的现代常见用法，“每个 CFG 都是 CSG”的说法在技术上是不正确的。但这只是一个技术问题：带有 lambda 产生式的 CFG 可以被机械地转换，就像一个非收缩语法可以被机械地转换成一个符合乔姆斯基定义的上下文相关的语法（参见 Wikipedia article on non-contracting grammars）。
（通过向 CFG 和 CSG 定义添加规则 S→λ 的例外，允许上下文相关和上下文无关语言都包含空字符串也很常见。）
备注
- 在乔姆斯基对上下文无关和敏感语法的表述中，解析树的含义是明确的，即使对于 CSG 也是如此；由于乔姆斯基是一位语言学家，并且正在寻找一个框架来解释自然语言的结构，因此解析树的概念很重要。您如何将
AB → BA的结果描述为解析树一点也不明显，尽管在a A b → B. 的情况下很清楚