敏感语法有一个空字符串？
在我的一个cs课程中，他们提到上下文无关语法和上下文敏感语法之间的区别在于，在CSG中，生产规则的左侧必须小于或等于右侧。
所以，他们给出的一个例子是上下文敏感的语法不能有一个空字符串，因为那么第一个规则就不会被满足。
然而，我知道常规语法包含在上下文无关中，上下文无关包含在上下文相关的文件中，上下文相关的文件包含在递归可枚举语法中。
因此，例如，如果语法是递归可枚举的，那么也是类型上下文敏感的，上下文无关和规则的。
问题是，如果发生这种情况，那么如果我有一个包含空字符串的上下文无关语法，那么它不会满足规则被视为一个上下文敏感，但然后会发生矛盾，因为每个上下文敏感是上下文无关的。
除了可能的顶级生产S → λ之外，空的生产（所谓的“lambda生产”，因为λ通常用于指空字符串）可以从任何上下文无关的语法中机械地消除。 这样做的算法很好地呈现在形式语言理论的每一篇文章中。
因此，对于任何带有lambda生成的CFG，都有一个没有lambda生成的等价CFG，它会生成相同的语言，并且这也是一个与上下文相关的语法。 因此，禁止CSG中的合同规则不会影响语言的层次结构：任何上下文无关的语言都是上下文敏感的语言。
乔姆斯基对上下文敏感语法的原始定义没有具体说明非收缩性质，而是更为严格的定义：每一个生产都必须是αAβ→αγβ的形式，其中A是单个符号， γ不是空的。 这组语法产生与非契约语法相同的语言集合（Chomsky也证明了这一点），但它不是同一套语言。 此外，他的上下文无关语法确实是上下文敏感语法的一个子集，因为通过他最初的CFG定义，lambda生成被禁止。 （1959年的论文可以在线获得，参见维基百科关于乔姆斯基层次结构的文章以获得参考链接。）
正是存在一个非空的上下文α和β这导致名称“上下文敏感”和“上下文无关”; 对于诸如AB→BA类的任意非约束规则而言，“上下文敏感”可能意味着什么也不太清楚。 （注1）
简而言之，考虑到您的问题中引用的CFG和CSG的通用现代用法，“每个CFG都是CSG”这一说法在技术上并不正确。 但这只是一个技术性问题：带有lambda生成的CFG可以进行机械转换，就像非契约语法可以机械地转换成符合乔姆斯基对上下文敏感的定义的语法一样（请参阅维基百科关于非契约语法的文章）。
（通过为CFG和CSG定义添加S→λ规则的例外，允许上下文敏感语言和上下文无关语言包含空字符串也很常见。）
笔记
AB → BA的结果描述为分析树，一点都不明显，尽管在例如a A b → B的情况下非常清楚。