recursion - 需要有关两种语言 S* 和 T* 的递归定义的帮助，其中 S={aa,b} 和 T={w1,w2,w3,w4}

Question

我目前正在学习自动机理论课程，但遇到了以下问题。我想出了第一个问题的答案，但对第二个问题的陈述感到困惑。

(i) 给出语言 S* 的递归定义，其中 S = {aa,b}。

第 1 步：Lamba、aa、b 在 S 中。

步骤 2：如果 x 在 S 中，那么 bx 和 xb 也是。

我想确认我的确认我的回答。

以下是我完全困惑的问题，无法想出答案。

(ii) 给出语言 T* 的递归定义，其中 T = {w1, w2, w3, w4} 其中这些 w 是一些特定的词。

Answer 1

(i) 非常接近。您至少缺少一条规则，并且您有一条不需要的规则。您需要xaa或aax在第 2 步中。您只需要在第 2 步中给出的规则之一，而不是两者。否则这是对的。一个最小的递归定义是：

1. lambda 在 S
2. 如果 x 在 S 中，则 aax 和 bx 在 S 中。

(ii) 同(i)，只是概括。答案是

1. lambda 在 T
2. 如果 x 在 T 中，则 w1x、w2x、w3x、w4x 在 T 中。