What is the concatenation of this language with itself?

Question

Given the following language:

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

That is, L1 = { ε ab, abab, ababab, abababab, ... }

The question is to find what language L12 is.

My guess is that it's equal to { (ab)2n | n ≥ 0 }. Is that correct? If so, how do I prove it? If not, why not?

Thanks!

Answer 1

The language L₁² is the language of all strings of the form xy, where x ∈ L₁ and y ∈ L₁. Note that x and y don't have to be the same strings; they can be chosen independently.

In fact, one option is that y = ε, since ε = (ab)⁰. Therefore, any string in L₁ must also belong to L₁², because we can always concatenate that string with ε.

Moreover, we can show that any string in L₁² is also in L₁. Take any string w ∈ L₁². It must have the form xy for some strings x, y ∈ L₁. This means that we can write w = xy = (ab)ⁿ(ab)^m for some natural numbers n and m. Accordingly, w = (ab)^n+m, and so w in L₁.

We just proved that L₁ ⊆ L₁² and that L₁² ⊆ L₁, from which we get that L₁ = L₁². This means that L₁² is the same language as L₁.

Hope this helps!