形式语言 - 语法
Formal Languages - Grammar
我正在学习形式语言和可计算性 class，但在理解语法概念时遇到了一些困难。我的作业问题之一是：
取∑={a,b}，设na(w)和nb(w)表示数分别是字符串 w 中的 a 和 b。然后语法 G 产生式：
S -> SS
S -> λ
S -> aSb
S -> bSa
生成语言 L = {w: na(w) = nb(w)}.
1) 示例中的语言包含一个空字符串。修改给定的语法，使其生成 L - {λ}.
我在想我应该修改L的条件，比如：
L = {w: na(w) = nb(w), na, nb > 0}
这样，我们就表明字符串永远不会为空。
2) 修改例子中的文法，使其生成L ∪ {anbn+1: n > = 0}.
- 我不确定该怎么做。这是否意味着我在语法中再添加一个条件，添加类似 S -> aSbb 的内容？
如果能对这两个问题做出任何解释，我们将不胜感激。我仍在尝试弄清楚这些语法问题，所以我不确定我的答案。
1) 问题是修改语法以获得新的语言；所以不要直接修改语言…
由于产生式，您的语法生成了空词：
S -> λ
所以你可以考虑完全删除这个作品。这会产生以下语法：
S -> SS
S -> aSb
S -> bSa
不幸的是，这个语法不会生成语言（有点像归纳法，它缺少一个首字母：没有只由终端组成的产生式）。要解决此问题，请添加以下作品：
S -> ab
S -> ba
2) 不要随意尝试添加生产规则，希望它能起作用。此处您需要 a 后跟 b。所以产生式规则
S -> bSa
肯定会消失。另外，规则
S -> SS
会产生，例如，abab（试着看看这是如何获得的）。所以我们也必须删除它。我们还剩下：
S -> λ
S -> aSb
现在这个语法生成：
λ
ab
aabb
aaabbb
等那还不错！为了获得额外的尾随 b，我们可以创建一个新的非终结符，比如 T，将我们当前的 S 替换为 T，并添加尾随 b 在 S:
T -> λ
T -> aTb
S -> Tb
我知道这是作业；我给了你作业的答案：那是因为，从你提问的方式来看，你似乎完全迷路了。我希望这个答案能帮助你走上正确的道路！
我正在学习形式语言和可计算性 class，但在理解语法概念时遇到了一些困难。我的作业问题之一是：
取∑={a,b}，设na(w)和nb(w)表示数分别是字符串 w 中的 a 和 b。然后语法 G 产生式：
S -> SS
S -> λ
S -> aSb
S -> bSa
生成语言 L = {w: na(w) = nb(w)}.
1) 示例中的语言包含一个空字符串。修改给定的语法，使其生成 L - {λ}.
我在想我应该修改L的条件，比如：
L = {w: na(w) = nb(w), na, nb > 0}
这样，我们就表明字符串永远不会为空。
2) 修改例子中的文法，使其生成L ∪ {anbn+1: n > = 0}.
- 我不确定该怎么做。这是否意味着我在语法中再添加一个条件，添加类似 S -> aSbb 的内容？
如果能对这两个问题做出任何解释，我们将不胜感激。我仍在尝试弄清楚这些语法问题，所以我不确定我的答案。
1) 问题是修改语法以获得新的语言；所以不要直接修改语言…
由于产生式，您的语法生成了空词：
S -> λ
所以你可以考虑完全删除这个作品。这会产生以下语法：
S -> SS
S -> aSb
S -> bSa
不幸的是，这个语法不会生成语言（有点像归纳法，它缺少一个首字母：没有只由终端组成的产生式）。要解决此问题，请添加以下作品：
S -> ab
S -> ba
2) 不要随意尝试添加生产规则，希望它能起作用。此处您需要 a 后跟 b。所以产生式规则
S -> bSa
肯定会消失。另外，规则
S -> SS
会产生，例如，abab（试着看看这是如何获得的）。所以我们也必须删除它。我们还剩下：
S -> λ
S -> aSb
现在这个语法生成：
λ
ab
aabb
aaabbb
等那还不错！为了获得额外的尾随 b，我们可以创建一个新的非终结符，比如 T，将我们当前的 S 替换为 T，并添加尾随 b 在 S:
T -> λ
T -> aTb
S -> Tb
我知道这是作业；我给了你作业的答案：那是因为，从你提问的方式来看，你似乎完全迷路了。我希望这个答案能帮助你走上正确的道路！