这种语言与自身的串联是什么？

Question

鉴于以下语言:

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

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

问题是要找到什么语言.L12

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

谢谢!

Answer 1

语言L ₁ ²是xy形式,其中x∈升的所有字符串的语言₁和y∈大号₁.请注意,x和y不必是相同的字符串; 它们可以独立选择.

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

此外,我们可以证明L ₁ ²中的任何字符串也在L _1中.采取任何字符串u∈大号₁ ².它必须有一些字符串X xy形式,Y∈大号₁.这意味着我们可以写W = XY =(AB)^Ñ(AB)^米一段自然数n和m.因此,w =(ab)^{n + m},因此w为L ₁.

我们只是证明使L ₁ ⊆大号₁ ²和使L ₁ ² ⊆大号₁,从中我们得到使L ₁ = L ₁ ².这意味着L ₁ ²与L _1的语言相同.

希望这可以帮助!