string - 通过递归生成集 - 语言和字符串(cs/logic)

Question

这是一个一般逻辑问题，是大多数入门语言和机器类(class)的常见问题。不过，我在互联网和论坛上搜索了有关此问题的任何帮助，但我似乎找不到详细说明连续集将包含哪些内容的主题。这是一个示例问题:(我有很多这样的硬件问题，我只是不知道从哪里开始)

设 L 为通过以下递归定义生成的 {a,b} 上的语言基础: λ ∈ L递归步骤:如果 w ∈ L 则 awbb 在 L 中。闭包:一个字符串 w ∈ L 仅当它可以通过有限数从基集中获得递归步骤的应用。A 部分。给出集合 L1； L2； L3由递归定义生成。请注意，L0 = λ

我知道字母表是 {a,b}，Lo = 空字符串，如果 L 中包含字符串 w，那么 awbb 就在 L 中。但这对于接下来的几个集合意味着什么？

我认为 L1 = {λ ,awbb} 那么 L2={λ , awbb, aawbbwbb} ？

如果您能就此提供任何帮助，我们将不胜感激。

Answer 1

我认为你误解了规则

If w ∈ L, then awbb ∈ L

的意思是。这并不意味着文字字符串“awbb”在 L 中。相反，它意味着如果您有某个字符串 w ∈ L，则可以将该字符串 w 替换为字符串 awbb，并且生成的字符串将在 L 中。对于例如，如果 ab ∈ L，则 aabbb ∈ L 也是如此。

使用它，尝试再次构造集合 L₁ 和 L₂。我认为一旦您完成了前几组，您就会立即发现一种模式。

希望这有帮助!