上下文敏感语法和上下文无关语法的区别

Question

Possible Duplicate: 上下文敏感语法和上下文无关语法 在我的教科书中，这两个术语的解释如下：

上下文敏感语法：

语法可以具有形式为w1→w2的产生式，其中w1=lAr，w2=lwr，其中A是非终端符号，l和r是零个或多个终端或非终端符号的字符串，w是非空的终端或非终端符号字符串。只要S不出现在任何其他产生式的右侧，它也可以具有S→λ的产生式。

上下文无关语法：

语法只能有形式为 w1 → w2 的产生式，其中 w1 是一个不是终端符号的单一符号。类型 3 的语法只能有形式为 w1 → w2 的产生式，其中 w1 = A，w2 = aB 或 w2 = a（其中 A 和 B 是非终端符号，a 是终端符号），或者 w1 = S，w2 = λ。

在我的教科书中，作者说：CSG 是 CFG 的特殊情况。但是，我不理解这一点。因为在 CSG 中，lAr -> lwr。l 和 r 可以是零个或多个终端或非终端的字符串。所以当它是一个零长度的字符串时，我们可以将 lAr 写成 A。因此，CSG 将成为 CFG。所以，CSG 是 CFG。

我是否理解错了什么？请纠正我。

谢谢 :)

- hqt

---

我会这样说——CFG是CSG的一种特殊情况。 - Vaughn Cato

这个答案可能会有帮助：https://dev59.com/Omsy5IYBdhLWcg3w6iNZ#8250104 - Milan Aggarwal

Answer 1

这本教材有误。就像您所说的，CFG是CSG的特例。

CSG可以表达比CFG更多的语言。

- nneonneo

---

请问你能多给我一些信息吗？因为我看到CSG对于上下文有一些限制，但CFG没有。所以我认为，CSG应该是CFG的特殊情况。 - hqt

你能给我一些例子，并告诉我它们的区别吗？谢谢 :) - hqt

CFG等价于CSG，其中每个规则的左右上下文都有一个空字符串。因此，每个CFG都可以被写成CSG，但不是每个CSG都可以被写成CFG。因此，根据定义，CFG是CSG的特殊情况。 - nneonneo