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

Question

Question

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

Engineering Computer-Science

0 0

Add a comment Transcribed image text

Answer 1

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.”