Formal Language Theory:

Let L be a non-empty Language over an alphabet Σ. Show that L² ⊆ L³ iff λ ∈ L.

I just need a kickstart in the right direction to know how to approach this.

Question

Formal Language Theory:

Let L be a non-empty Language over an alphabet Σ. Show that L² ⊆ L³ iff λ ∈ L.

I just need a kickstart in the right direction to know how to approach this.

_euler_ · Answer

λ is the empty string btw

holsteremission · Answer

Is $L^n$ a concatenation of $L$ with itself $n$ times, or is there another meaning behind that "product"?

_euler_ · Answer

@HolsterEmission

Your assumption is correct. It is concatenation.

Thanks for taking a look at this (:

holsteremission · Answer

Forward direction: Suppose $x$ is some word in $L^2$. Because $L^2\subseteq L^3$, that means $x\in L^3$.

Given that $x\in L^2$, there are some $x_i,x_j\in L$ such that $x=x_ix_j\in L^2$. With $x\in L^3$, this means one of the following are true:
    (1) $x=x_ix_j\lambda$
    (2) $x=x_i\lambda x_j$
    (3) $x=\lambda x_ix_j$
and all possibilities point to $\lambda\in L$.

Reverse direction: Starting with the assumption that $\lambda\in L$, you can concatenate $\lambda$ with any $x\in L^2$ to see that $x\lambda=\lambda x=x\in L^3$, so $L^2\subseteq L^3$.

_euler_ · Answer

Looks perfectly good. Thank you (: