上下文无关语言中的 1 或 2 个右侧变量
1 or 2 right hand side variable in Context free language
我有2个问题要问，我也有一些想法。
1) X-Context free grammer(X-CFG) 在每个规则的右侧有 1 个终端或变量。
2) Y-CFG 在每个规则的右侧有 2 个终端或变量。
问题：
a) 他们会生成任何非常规语言吗？证明.
b) 他们生成所有常规语言吗？证明.
答案：
a) 我认为对于 X-CFG，他们不能生成任何非常规语言，因为它只能生成有限数量的字符串，所以他们不能生成任何非常规语言。
b) 像 a^* 这样的正则语言有无数种。我们也不能用CFG生成无限的字符串，所以可以说它不能生成所有的正则语言。
我说得对吗？
我对b题一无所知
考虑 Y-CFG：
S → aA
S → ab
A → Sb
这不是满足你的约束生成非常规语言的Y-CFG吗？ an bn 使得 n >= 1
另请参阅 this，因为它指出：
Every regular grammar is context-free, but not all context-free grammars are regular. And explains a little why with an example to help grasp it.
所以如果我理解正确的话，我相信你的两个答案都是错误的。
更新
每个常规语法都是上下文无关的。那么问题是我们可以使用 2 个变量定义所有 CFG（t 是终端，N 是非终端）：
S → SS
S → t
S → N
S → tN
S → Nt
因此我们可以定义终止的东西，从多个起始字符串中生长出来的东西，在前面生长的东西和在后面生长的东西。这是 CFG 中的每个案例。所以我会说是的，你可以生成所有常规语言。
我有2个问题要问，我也有一些想法。
1) X-Context free grammer(X-CFG) 在每个规则的右侧有 1 个终端或变量。
2) Y-CFG 在每个规则的右侧有 2 个终端或变量。
问题：
a) 他们会生成任何非常规语言吗？证明.
b) 他们生成所有常规语言吗？证明.
答案：
a) 我认为对于 X-CFG，他们不能生成任何非常规语言，因为它只能生成有限数量的字符串，所以他们不能生成任何非常规语言。
b) 像 a^* 这样的正则语言有无数种。我们也不能用CFG生成无限的字符串，所以可以说它不能生成所有的正则语言。
我说得对吗？
我对b题一无所知
考虑 Y-CFG：
S → aA S → ab A → Sb
这不是满足你的约束生成非常规语言的Y-CFG吗？ an bn 使得 n >= 1
另请参阅 this，因为它指出：
Every regular grammar is context-free, but not all context-free grammars are regular. And explains a little why with an example to help grasp it.
所以如果我理解正确的话，我相信你的两个答案都是错误的。
更新
每个常规语法都是上下文无关的。那么问题是我们可以使用 2 个变量定义所有 CFG（t 是终端，N 是非终端）：
S → SS S → t S → N S → tN S → Nt
因此我们可以定义终止的东西，从多个起始字符串中生长出来的东西，在前面生长的东西和在后面生长的东西。这是 CFG 中的每个案例。所以我会说是的，你可以生成所有常规语言。