Formal Languages - Grammar

Question

我正在学习形式语言和可计算性课程，并且在理解语法概念时遇到了一些麻烦。我的一个分配的问题是这样的：

取Σ= {A，B}，并且设N _一个（W）和正 _b（W）表示字符串u在A和B的数量，分别。然后文法G与制作：

S -> SS 
S -> λ 
S -> aSb 
S -> bSa 

生成语言L = {瓦特：N _一个（W）= N _b（W）}。

1）示例中的语言包含空字符串。修改给定的语法，使其生成L - {λ}。

• 我在想，我应该修改L的条件下，是这样的：

  L = {黑白：ñ_一个（W）= N _b（W），N _一，n _b> 0}

  这样，我们指出该字符串永远不会为空。

2）修改语法的例子中，这样它会生成L个∪{一个^Ñ b ^{n + 1个}：N> = 0}。

• 我不确定如何做到这一点。这是否意味着我在语法中增加了一个条件，如S - > aSbb？

任何关于这两个问题的解释将不胜感激。我仍然试图找出这些语法问题，所以我不确定我的答案。

Answer 1

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 

---

我知道，这是家庭作业;我给了你作业的解决方案：那是因为，从你提出问题的方式来看，你似乎完全失去了。我希望这个答案能帮助你走上正确的道路！