Question

Let L be any non-empty language over an alphabet Σ. Show that L^2⊆L^3 if and only if λ∈L.

Answer 1

Solution for the problem is provided below, please comment if any doubts:

Here we need to prove that, “L^2⊆L^3 if and only if λ∈L.”

Proof by contradiction:

• First assume that λ not belongs to L
• L^2 is generated by concatenating all the strings of “L” with all strings of “L” itself.
• If L has “n” strings, then L^2 will have “n²” strings in it.
• Since the empty string λ not belongs to L, no strings in L will be there in L^2, because the strings will we L^2⊆L^3 concatenated with non empty strings.
• L^3 is generated by concatenating strings in L^2 by strings I L.
• Since λ not there in L, the strings in L^3 will be an extended version of L^2 strings by concatenating it with strings in L.
• That is L^3 will not contain the strings of L^2.
• That is L^2 is can’t be the sub set of L^3 if λ not belongs to L.
• That is our assumption is wrong.

That is, “L^2⊆L^3 if and only if λ∈L.”