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

Question

这是一个普遍的逻辑问题,对于大多数入门语言和机器课程来说都很常见.然而,我已经在互联网和论坛上搜索了这方面的任何帮助,但我似乎无法找到一个主题,详细说明连续集将包含什么.这是一个示例问题:(我有很多这样的硬件问题,我只是不知道从哪里开始)

设L是由以下递归定义基础生成的{a,b}语言:λ∈L递归步骤:如果w∈L则awbb在L闭包中:只有在可以从中得到的字符串w∈L由递归步骤的有限数量的应用程序设置的基础.第一部分 给出集L1; L2; 和递归定义生成的L3.注意L0 =λ

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

我认为L1 = {λ,awbb}然后L2 = {λ,awbb,aawbbwbb}？

您可以提供的任何帮助将不胜感激.

Answer 1

我认为你误解了规则

如果w∈L,那么awbb∈L

手段.这并不意味着文字字符串"awbb"在L中.相反,它意味着如果你有一些字符串w∈L,你可以将字符串w替换为字符串awbb,结果字符串将在L中.例如,如果ab∈L,那么aabbb∈L也是如此.

使用它,尝试再次构建集合L ₁和L ₂.我认为,一旦你建立了前几套,你就会发现一个直接的模式.

希望这可以帮助!