math - この言語とそれ自体の連結は何ですか?

Question

次の言語が与えられた場合:

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

あれは、L1 = { ε ab, abab, ababab, abababab, ... }

問題は、言語が何であるかを見つけることです。L12

に等しいと思います。あれは正しいですか？もしそうなら、どうやってそれを証明するのですか？そうでない場合、なぜですか？{ (ab)2n | n ≥ 0 }

ありがとう！

Answer 1

言語 L ₁ ^{2は、x ∈ L} ₁および y ∈ L ₁である xy 形式のすべての文字列の言語です。x と y は同じ文字列である必要はありません。それらは独立して選択できます。

実際、ε = (ab) ⁰であるため、1 つのオプションは y = εです。したがって、L 1 内の任意の文字列_{もL 1} ²に属している必要があります。これは、その文字列を常に ε と連結できるためです。

さらに、L ₁ ²の任意の文字列もL ₁にあることを示すことができます。任意の文字列 w ∈ L ₁ ²を取ります。_{いくつかの文字列 x, y ∈ L 1}に対して xy の形式を持たなければなりません。これは、自然数 n と m に対してw = xy = (ab) ⁿ (ab) ^{mと書けることを意味します。}したがって、w = (ab) ^n+mであり、L ₁の wです。

_{L 1} ⊆ L ₁ ²と L ₁ ² ⊆ L ₁を証明したところ、L ₁ = L ₁ ²が得られました。これは、L ₁ ^{2が L} ₁と同じ言語であることを意味します。

お役に立てれば！