How can a formal language $L$ concatenated with itself $L^k$ ever equal $L^{k+1}$

Question

I’m seeking an explanation of how any formal language L concatenated with itself $k$ times, $L^k$, can equal that same language concatenated with itself $k+1$ times, $L^{k+1}$.

The problem I’m working on specifically asks for me to provide some language $L$ over $Σ={a}$ such that $L^3 = L^4$, but $L \neq L^2$ and $L^2 \neq L^3$. Intuitively, this does not make sense to me. Seemingly $L^{k+1}$ should always be greater in cardinality than $L^k$, and thus be unequal. I assume that the answer relates to the null string being in $L$, but I am not sure how or why.

Could anyone clarify where my intuition is leading me astray? Thank you for any insight.

Answer 1

Take e.g. $L=\{\varepsilon,a,aaaa,aaaaa,aaaaaa,\ldots\}$.

Answer 2

Clearly, if the shortest word in $L$ has length $n$, then the shortest word in $L^k$ has length $kn$. So if $\epsilon\notin L$ then $L^k\ne L^{k+1}$ as $kn\ne (k+1)n$. On the other hand, if the null string $\epsilon$ is in $L$ then $L^k\subseteq L^{k+1}$, but not necessarily $L^k= L^{k+1}$ (which you don't want for $k=1$ and $k=2$ anyway).

Assume we have a language $L_0$ such that $L_0^2=L_0$ and a word $\alpha$ such that $\alpha,\alpha^2,\alpha^3\notin L_0$, but $\alpha^4\in L_0$. Then $L=L_0\cup\{\alpha\}$ does the job (why?). Now observe that you can pick for example $L_0=(aaaa)^*=\{\,a^{4n}\mid n\in\mathbb N_0\,\}$ and $\alpha=a$.