math - 这种语言与其自身的连接是什么？

Question

给定以下语言：

L1 = { (ab)n | n ≥ 0 }

那是，L1 = { ε ab, abab, ababab, abababab, ... }

问题是找出什么是语言。L12

我的猜测是它等于。那是对的吗？如果是这样，我该如何证明？如果不是，为什么不呢？{ (ab)2n | n ≥ 0 }

谢谢！

Answer 1

语言 L ₁ ²是所有形式为 xy 的字符串的语言，其中 x ∈ L ₁和 y ∈ L ₁。请注意，x 和 y 不必是相同的字符串；它们可以独立选择。

事实上，一种选择是 y = ε，因为 ε = (ab) ⁰。因此，L 1 中的任何字符串_也必须属于 L ₁ ²，因为我们总是可以将该字符串与 ε 连接起来。

此外，我们可以证明 L ₁ ²中的任何字符串也在 L ₁中。取任意字符串 w ∈ L ₁ ²。_{对于某些字符串 x, y ∈ L 1}，它必须具有 xy 形式。这意味着我们可以为一些自然数 n 和 m写出 w = xy = (ab) ⁿ (ab) ^{m 。}因此，w = (ab) ^n+m，因此 L ₁中的 w 。

我们刚刚证明了 L ₁ ⊆ L ₁ ²和 L ₁ ² ⊆ L ₁，从中我们得到 L ₁ = L ₁ ²。这意味着 L ₁ ^{2是与 L} ₁相同的语言。

希望这可以帮助！